LeetCode: Min Stack

思路分析

同样是非常经典的面试题目，要求实现一个栈，额外支持一个取最小值的操作，并且时间复杂度为O(1)。思路太经典就不分析了，双栈思想，一个记录正常值一个记录出现过的最小值。

但是这题LeetCode的OJ对内存卡得比较死，需要做一个小小的优化，就是说当入栈的值大于已经出现过的最小值时，就不把它加入记录最小值的栈中。同样，出栈的时候，只有当前出栈元素等于最小值栈的栈顶元素时，才对最小值栈出栈。

代码

class MinStack {
public:
    stack<int> stk, _min;
    void push(int x) {
        stk.push(x);
        if ( _min.size() == 0 || x <= _min.top() )
            _min.push(x);
    }

    void pop() {
        if ( stk.top() == _min.top() ) _min.pop();
        stk.pop();
    }

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

    int getMin() {
        return _min.top();
    }
};