[Leetcode] Min Stack, Solution

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

[Thoughts]
这其实需要一个栈和数组的联合数据结构。数组用于存储数据，而栈用于记录当前最小值，用于服务getMin().

[Code]

1:  class MinStack {  
2:      
3:    stack<int> min_index;  
4:    vector<int> values;  
5:      
6:  public:  
7:      
8:      
9:    /** initialize your data structure here. */  
10:    MinStack() {  
11:        
12:    }  
13:      
14:    void push(int x) {  
15:      if(values.size() == 0) {  
16:        values.push_back(x);  
17:        min_index.push(values.size()-1);  
18:        return;  
19:      }  
20:        
21:      int cur_min = min_index.top();  
22:      values.push_back(x);  
23:      if(x > values[cur_min]) {  
24:        min_index.push(cur_min);  
25:      } else {  
26:        min_index.push(values.size()-1);  
27:      }  
28:        
29:    }  
30:      
31:    void pop() {  
32:      values.pop_back();  
33:      min_index.pop();  
34:    }  
35:      
36:    int top() {  
37:      return values[values.size()-1];  
38:    }  
39:      
40:    int getMin() {  
41:      return values[min_index.top()];  
42:    }  
43:  };  
44:    
45:  /**  
46:   * Your MinStack object will be instantiated and called as such:  
47:   * MinStack obj = new MinStack();  
48:   * obj.push(x);  
49:   * obj.pop();  
50:   * int param_3 = obj.top();  
51:   * int param_4 = obj.getMin();  
52:   */