题目
设计一个支持push，pop，top等操作并且可以在O(1)时间内检索出最小元素的堆栈。

• push(x)–将元素x插入栈中
• pop()–移除栈顶元素
• top()–得到栈顶元素
• getMin()–得到栈中最小元素

样例
MinStack minStack = new MinStack();
minStack.push(-1);
minStack.push(3);
minStack.push(-4);
minStack.getMin(); —> Returns -4.
minStack.pop();
minStack.top(); —> Returns 3.
minStack.getMin(); —> Returns -1.

解法：单调栈

得到栈中最小元素这个操作常规栈是不支持的
由于在元素弹出栈的过程中，最小元素会不断变化，因此仅仅只用一个变量保存最小值是不够的，此时可以引入一个辅助的单调栈M
单调栈中可以每次push都存入M栈顶和当前元素中的较小者，pop时直接pop两个栈
也可以只向M中push比栈顶更小的元素，pop时两个栈顶元素相同才pop M
时间复杂度O(1)，空间复杂度O(n)

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> s, s_min;
    MinStack() {
    }
    void push(int x) {
        s.push(x);
        if (s_min.empty() || x < s_min.top()) 
            s_min.push(x);
    }
    void pop() {
        if (s_min.top() == s.top()) {
            s_min.pop();
        }
        s.pop();
    }
    int top() {
        return s.top();
    }
    int getMin() {
        return s_min.top();
    }
};
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */