【程序员面试金典】面试题 03.02. 栈的最小值

思路

借助辅助栈保存当前栈最小值。

• 入栈：如果入栈元素小于最小栈的栈顶元素，则同时加入最小栈；否则，将最小栈栈顶元素再次加入最下栈
• 出栈：同时弹出两个栈中元素

代码

时间复杂度：O(1)
空间复杂度：O(1)

class MinStack {
    stack<int> st1;
    stack<int> st2;
public:
    /** initialize your data structure here. */
    MinStack() {

    }
    
    void push(int x) {
        st1.push(x);
        if (!st2.empty()) {
            if (x < st2.top()) st2.push(x);
            else st2.push(st2.top());
        } else {
            st2.push(x);
        }
    }
    
    void pop() {
        if (!st1.empty()) {
            st1.pop();
            st2.pop();
        }        
    }
    
    int top() {
        if (!st1.empty()) return st1.top();
        return -1;
    }
    
    int getMin() {
        if (!st2.empty()) return st2.top();
        return -1;
    }
};