题目

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

• push(x) -- 将元素 x 推入栈中。
• pop() -- 删除栈顶的元素。
• top() -- 获取栈顶元素。
• getMin() -- 检索栈中的最小元素。

示例：

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3
minStack.pop();
minStack.top(); --> 返回 0
minStack.getMin(); --> 返回 -2

思路

因为需要在常数时间内完成，所以基本思想就是以空间换时间，因此使用辅助栈是常见的方法。使用辅助栈需要注意数据同步问题，当辅助栈为空时，有新元素来就压入。不为空时，普通栈压入一个元素，需要与辅助栈的顶比较，如果小于等于就压入。对于pop，每当弹出时与辅助栈顶进行比较，相同才弹出。

也可以不使用辅助栈，只使用一个栈，通过每次压入两个值（新值和最小值），出栈时弹出两个值。对于top，用一个最小值变量保存弹出的最小值，取出顶部后再将其压入。

解答

1.辅助栈：

class MinStack {
public:
    stack<int> sta; //普通栈
    stack<int> min; //最小栈

    void push(int x) {
        sta.push(x);
        if(min.empty() || x <= min.top()) 
            min.push(x);
    }
    
    void pop() {
        if(min.top() == sta.top()) 
            min.pop();
        sta.pop();
    }
    
    int top() {
        return sta.top();
    }
    
    int getMin() {
        return min.top();
    }
};

【关注公众号DoCode，每日一道LeetCode，将零碎时间利用起来】