LeetCode155. 最小栈

要能够在常数时间内检索到栈内最小元素，我们可以额外开一个栈，这个额外的栈的栈顶元素存放目前栈内的最小元素，每次栈内压入一个新元素，辅助栈也压入一个元素，也就是把新元素和原栈顶元素比较，较小的那个就是新的最小元素，压入辅助栈的栈顶；原栈弹出栈顶元素的时候，辅助栈也弹出栈顶元素，这样，不管什么时候，辅助栈的栈顶元素总是存放原栈当前的栈内最小元素。

题目说了，push、pop和getMin操作总是在非空栈上调用，所以不需要做特判。

不过，由于辅助栈每次压入的元素都是新元素和原栈顶元素的最小值，这样，当压入第一个元素的时候，就是新元素和一个空栈顶进行比较，这是不行的，所以我们初始化在辅助栈minSt里压入一个INT_MAX，这样辅助栈第一个元素就是原栈的第一个元素和INT_MAX之间的较小值（还是第一个元素），这样就把边界情况处理了。

代码如下：

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> st, minSt;
    MinStack() {
        minSt.push(INT_MAX);
    }
    
    void push(int x) {
        st.push(x);
        minSt.push(min(x, minSt.top()));
    }
    
    void pop() {
        st.pop();
        minSt.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return minSt.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();
 */