[LeetCode] Min Stack

The idea is to use two stacks.

For push, the first stack records the pushed elements and the second stack records all the minimum (including duplicates) that have been seen.

For pop, we need to compare with the top elements of the two stacks. If they are equal (the top element is also minimum, popping it out will change the minimum), pop both; otherwise, only pop the first stack.

The remaining top and getMin will be trivial: just return the top element of the first and second stack respectively.

The code is as follows.

 1 class MinStack {
 2 public:
 3     void push(int x) {
 4         if (stk1.empty() || x <= stk2.top())
 5             stk2.push(x);
 6         stk1.push(x);
 7     }
 8 
 9     void pop() {
10         if (stk1.top() == stk2.top())
11             stk2.pop();
12         stk1.pop();
13     }
14 
15     int top() {
16         return stk1.top();
17     }
18 
19     int getMin() {
20         return stk2.top();
21     }
22 private:
23     stack<int> stk1; 
24     stack<int> stk2;
25 };