最小栈

分类：LeetCode 标签：栈设计发布于：2019-10-20 ID：155

难度：简单
通过率： 34.7%
题目链接：https://leetcode-cn.com/problems/min-stack

题目描述

设计一个支持 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.

解法：

首先请假想一组数字，并在纸上模拟入栈的过程。在此过程中，能够很轻易地发现，只需要记录下先前入栈的数中的最小值，用此最小值和当前待入栈的数比较，就可以得到当前数入栈后栈中的最小值。

但是如果入栈和出栈穿插进行，如果最小值被出栈了，那么栈中余下的数中最小值就不得而知了。但是，可以在每次入栈时把当前值和最小值作为一个元组入栈，即每次入栈的是 (value, min)。栈顶的元素的 min 就是当前栈中的最小值。有新的数字入栈时，和栈顶元素的中 min 比较，计算出最小值即可。这样，有元素出栈后，栈顶元素中的 min 依然是栈中的最小值。

class MinStack {
public:
    void push(int val) {
        int min_val = val;
        if(!stack.empty()){
            min_val = ::min(val, stack.top()[1]);
        }
        stack.push({val, min_val});
    }

    void pop() {
        stack.pop();
    }

    int top() {
        return stack.top()[0];
    }

    int min() {
        return stack.top()[1];
    }

private:
    stack<array<int, 2>> stack;
};

上面这个方法，时间复杂度上完全达标，空间是常规的栈的二倍。下面考虑如何在空间复杂度上优化。

如果入栈的数比最小值要大，那么最小值是不变的。如果入栈的数小于最小值，那么最小值需要被更新。在出栈的时候，如果当前值等于最小值，则需要把最小值更新为前一个最小值。基于以上考虑，需要记录下历史上的最小值，这是一个递减的序列，且需要在序列后面加入或者删除值，这个序列的操作符合栈的特性。

基于以上分析，只需要使用另外一个栈，叫做 stack_min，用来保存历史上产生过的最小值。stack_min 的栈顶保存的是目前最小栈中的最小值，基于该最小值与新插入的值进行比较，就可以决定是否插入新的最小值。出栈的时候，如果出栈元素等于 stack_min 的栈顶元素，那就出栈。

class MinStack {
public:
    void push(int val) {
        stack_val.push(val);

        if(stack_min.empty() || stack_min.top() >= val){
            stack_min.push(val);
        }
    }

    void pop() {
        if(stack_val.top() == stack_min.top()){
            stack_min.pop();
        }
        stack_val.pop();
    }
    
    int top() {
        return stack_val.top();
    }

    int min() {
        return stack_min.top();
    }

private:
    stack<int> stack_val;
    stack<int> stack_min;
};

LeetCode 题解

积跬步，至千里。

最小栈

题目描述

解法：