问题

实现一个最小栈

算法：单调栈

经典题。要维护一个单调栈，随时能输出最小值，比当前最小值大且靠后的元素肯定不可能作为最小值输出，故舍弃，这样就形成了单调递减栈

复杂度

$O(N)$

代码

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

    }

    void push(int x) {
        stk1.push(x);
        if(stk2.empty() || stk2.top() >= x) stk2.push(x);
    }

    void pop() {
        if(stk1.top() == stk2.top()) stk2.pop();
        stk1.pop();
    }

    int top() {
        return stk1.top();
    }

    int min() { 
        return stk2.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->min();
 */