Description:
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.
Link:
https://leetcode.com/problems/min-stack/#/description
解题方法：
方法来源：https://discuss.leetcode.com/topic/18556/c-using-two-stacks-quite-short-and-easy-to-understand
使用2个栈s1，s2:
s1负责正常栈的储存。
s2储存每次出现最小的数的。
这样当s1删除到最小的数的时候，s2也删除栈顶的数。这样可以保证s2的栈顶一直是当前最小数。因为即使s1里面包含的当前第二小的数而s2不包含，需要用到这个第二小的数的时候，这个数早就被删除了。比如：
s1: 栈顶(2->1->3->4);
s2: 栈顶(1->3->4);
当删除1时，2早就不在s1中，所以接下来最小数是3。
Tips:
如果在面试中不允许使用stack，自己写List也可以实现这个方法。
Time Complexity：
O(1)
完整代码：
class MinStack {
private:
stack<int> s1;
stack<int> s2;
public:
void push(int x) {
s1.push(x);
if (s2.empty() || x <= getMin()) s2.push(x);
}
void pop() {
if (s1.top() == getMin()) s2.pop();
s1.pop();
}
int top() {
return s1.top();
}
int getMin() {
return s2.top();
}
};
