## Monday, August 7, 2017

### [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]

[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:   */
``````