155. 最小栈

力扣题目链接 (opens new window)

题目描述

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

实现 MinStack 类：

• MinStack() 初始化堆栈对象
• void push(int val) 将元素 val 推入堆栈
• void pop() 删除堆栈顶部的元素
• int top() 获取堆栈顶部的元素
• int getMin() 获取堆栈中的最小元素

示例 1：

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // 返回 -3
minStack.pop();
minStack.top();    // 返回 0
minStack.getMin(); // 返回 -2

提示：

• -2^31 <= val <= 2^31 - 1
• pop、top 和 getMin 操作总是在非空栈上调用
• push、pop、top 和 getMin 最多被调用 3 * 10^4 次

思路

普通栈已经能在 O(1) 时间内完成 push、pop 和 top，难点只剩一个：怎样在 O(1) 时间内得到当前栈中的最小值？

最直观的做法是，每次调用 getMin() 都遍历整个栈。这样不需要额外空间，但一次查询的时间复杂度是 O(n)，不符合题目要求。

有录友可能会想到，只用一个变量记录最小值。压栈时确实容易更新：

minValue = min(minValue, val)

但如果当前最小值被弹出了，新的最小值是谁？只记录一个值，我们已经找不回之前的最小值了。

所以问题的关键不是只记录“现在最小的是谁”，而是要记录：栈处于每一个历史状态时，最小值分别是谁。

辅助栈

我们再准备一个最小值栈 minStack：

• 数据栈 stack 正常保存所有元素
• 最小值栈 minStack 的每个位置，保存数据栈到对应位置为止的最小值

每次压入 val 时：

1. 数据栈压入 val
2. 如果最小值栈为空，最小值栈也压入 val
3. 否则压入 min(val, minStack.top())

每次弹出时，两个栈同步弹出。这样无论数据栈回到哪一个历史状态，最小值栈的栈顶都会一起回到当时的最小值。

两个栈始终等长，并且 minStack.top() 始终表示当前数据栈的最小值。

为什么最小值栈要在每次 push 时都压入一个值，包括压入重复的最小值？

因为这样两个栈可以完全同步，pop() 不需要判断弹出的元素是不是最小值，直接同时弹出即可。逻辑简单，也不容易在重复最小值上出错。

模拟过程

以题目示例为例，依次执行：

push(-2), push(0), push(-3)

两个栈的变化如下：

操作	数据栈（栈底 → 栈顶）	最小值栈（栈底 → 栈顶）	当前最小值
push(-2)	[-2]	[-2]	-2
push(0)	[-2, 0]	[-2, -2]	-2
push(-3)	[-2, 0, -3]	[-2, -2, -3]	-3

注意压入 0 时，最小值仍然是 -2，所以最小值栈再次压入 -2。压入 -3 后，最小值栈顶更新为 -3，此时 getMin() 直接返回 -3。

接着执行 pop()，数据栈弹出 -3，最小值栈也弹出 -3：

数据栈：   [-2, 0]
最小值栈： [-2, -2]

此时 top() 返回 0，而 getMin() 读取最小值栈顶，返回 -2。不需要重新遍历，之前的最小值自然就恢复了。

解题代码

C++

class MinStack {
private:
    stack<int> st;
    stack<int> minSt;

public:
    MinStack() {
    }

    void push(int val) {
        st.push(val);

        // 记录数据栈处于当前状态时的最小值
        if (minSt.empty()) {
            minSt.push(val);
        } else {
            minSt.push(min(val, minSt.top()));
        }
    }

    void pop() {
        // 两个栈同步弹出，恢复到上一个状态
        st.pop();
        minSt.pop();
    }

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

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

复杂度分析

• 时间复杂度：push、pop、top、getMin 均为 O(1)。
• 空间复杂度：O(n)。数据栈和最小值栈都最多保存 n 个元素。

其他语言

Python3

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)

        # 记录数据栈处于当前状态时的最小值
        if not self.min_stack:
            self.min_stack.append(val)
        else:
            self.min_stack.append(min(val, self.min_stack[-1]))

    def pop(self) -> None:
        # 两个栈同步弹出，恢复到上一个状态
        self.stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

Java

import java.util.ArrayDeque;
import java.util.Deque;

class MinStack {
    private final Deque<Integer> stack;
    private final Deque<Integer> minStack;

    public MinStack() {
        stack = new ArrayDeque<>();
        minStack = new ArrayDeque<>();
    }

    public void push(int val) {
        stack.push(val);

        // 记录数据栈处于当前状态时的最小值
        if (minStack.isEmpty()) {
            minStack.push(val);
        } else {
            minStack.push(Math.min(val, minStack.peek()));
        }
    }

    public void pop() {
        // 两个栈同步弹出，恢复到上一个状态
        stack.pop();
        minStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

Go

type MinStack struct {
    stack    []int
    minStack []int
}

func Constructor() MinStack {
    return MinStack{
        stack:    make([]int, 0),
        minStack: make([]int, 0),
    }
}

func (this *MinStack) Push(val int) {
    this.stack = append(this.stack, val)

    // 记录数据栈处于当前状态时的最小值
    if len(this.minStack) == 0 {
        this.minStack = append(this.minStack, val)
    } else {
        currentMin := this.minStack[len(this.minStack)-1]
        if val < currentMin {
            currentMin = val
        }
        this.minStack = append(this.minStack, currentMin)
    }
}

func (this *MinStack) Pop() {
    // 两个栈同步弹出，恢复到上一个状态
    this.stack = this.stack[:len(this.stack)-1]
    this.minStack = this.minStack[:len(this.minStack)-1]
}

func (this *MinStack) Top() int {
    return this.stack[len(this.stack)-1]
}

func (this *MinStack) GetMin() int {
    return this.minStack[len(this.minStack)-1]
}

JS

var MinStack = function() {
    this.stack = [];
    this.minStack = [];
};

MinStack.prototype.push = function(val) {
    this.stack.push(val);

    // 记录数据栈处于当前状态时的最小值
    if (this.minStack.length === 0) {
        this.minStack.push(val);
    } else {
        const currentMin = this.minStack[this.minStack.length - 1];
        this.minStack.push(Math.min(val, currentMin));
    }
};

MinStack.prototype.pop = function() {
    // 两个栈同步弹出，恢复到上一个状态
    this.stack.pop();
    this.minStack.pop();
};

MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1];
};

MinStack.prototype.getMin = function() {
    return this.minStack[this.minStack.length - 1];
};

扩展：只在最小值变化时入栈

辅助栈还可以只保存“成为过最小值”的元素：

• push 时，只有当 val <= minStack.top() 时才压入最小值栈
• pop 时，如果数据栈栈顶等于最小值栈栈顶，两个栈才一起弹出

这里一定要写 <=，不能写 <。例如连续压入两个相同的最小值，只记录一次的话，弹出其中一个以后，另一个明明还在数据栈里，最小值栈却已经空了。

这种写法在很多数据不影响最小值时更省空间，但分支更多。面试中我更推荐上面的同步写法，关系直观，不容易写错。

与代码随想录联系

本题和20. 有效的括号都使用了栈的“后进先出”，但解决的问题不同：

• 有效的括号用栈保存尚未匹配的信息
• 最小栈用辅助栈保存每一个历史状态的最小值

做完本题，可以继续学习739. 每日温度。每日温度会进一步利用栈内元素的单调关系，寻找右侧第一个更大的元素。