155. 最小栈
155. 最小栈
题目链接（中等）
题目描述
设计一个支持 push、pop、top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类：
MinStack()：初始化堆栈对象；void push(int value)：将元素value推入堆栈；void pop()：删除堆栈顶部的元素；int top()：获取堆栈顶部的元素；int getMin()：获取堆栈中的最小元素。
数据范围：
-2^31 <= val <= 2^31 - 1pop、top和getMin操作总是在 非空栈 上调用push、pop、top、getMin最多被调用3 * 10^4次
示例
输入：
["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.核心思路
难点在于：普通栈的 push、pop、top 都是 $O(1)$，但 getMin 要 $O(1)$。
关键观察：栈是后进先出的。如果元素 a 在入栈时，栈里还有 b, c, d，那么只要 a 还在栈里，b, c, d 就一定也在栈里（因为 a 不弹出之前，它下面那些元素不会被弹出）。
推论：每个元素入栈时，栈内的最小值是确定的。只要记录下这个最小值，将来这个元素成为栈顶时，就可以直接返回当时记录的最小值。
因此可以用一个辅助栈，与元素栈同步插入和删除，专门存「当前元素对应的最小值」。
方法一：辅助栈
思路及解法
维护两个栈：
stack：存所有元素；min_stack：存「每个元素入栈时，栈内的最小值」。
两个栈长度始终相同，操作一一对应：
push(x)：- 元素栈压入
x； - 辅助栈压入
min(x, min_stack[-1])，即「当前元素和之前的最小值中更小的那个」；
- 元素栈压入
pop()：两个栈同时弹出栈顶；top()：返回stack[-1]；getMin()：返回min_stack[-1]，即当前栈内最小值。
辅助栈初始化：为了让 push 时 min_stack[-1] 总有值，可以放一个 inf（正无穷）在辅助栈底部，或者用一个标志位处理「空栈」情况。
举例：依次 push -2, 0, -3
| 操作 | stack |
min_stack |
|---|---|---|
| push(-2) | [-2] |
[inf, -2] |
| push(0) | [-2, 0] |
[inf, -2, -2] |
| push(-3) | [-2, 0, -3] |
[inf, -2, -2, -3] |
| pop() | [-2, 0] |
[inf, -2, -2] |
| top() | 返回 0 | — |
| getMin() | — | 返回 -2 |
可以看到，辅助栈每个位置都存着「到该位置为止栈内的最小值」，与元素栈一一对应。
代码
import math
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = [math.inf] # 哨兵，避免空栈判断
def push(self, val: int) -> None:
self.stack.append(val)
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]复杂度分析
- 时间复杂度：所有操作均为 $O(1)$，每个操作最多调用两次栈的插入/删除。
- 空间复杂度：$O(n)$，两个栈最坏情况下都存 $n$ 个元素。
方法二：单栈存差值（不用辅助栈）
思路及解法
用一个栈保存「元素与当前最小值的差值」，再用一个变量 min_val 记录当前最小值。
push(x)：- 若栈为空：
min_val = x，压入0； - 否则压入
x - min_val，若x < min_val则更新min_val = x；
- 若栈为空：
pop()：弹出差值d：- 若
d >= 0，说明弹出的是普通元素，最小值不变； - 若
d < 0，说明弹出的元素就是当时的最小值，需要还原：min_val = min_val - d；
- 若
top()：- 若栈顶差值
d >= 0，返回min_val + d； - 若
d < 0，说明栈顶就是min_val，直接返回min_val；
- 若栈顶差值
getMin()：返回min_val。
优点：只用一个栈，空间省一半。
缺点：差值可能溢出（Python 无整数溢出，但 C++/Java 需要注意），逻辑略绕。
代码
class MinStack:
def __init__(self):
self.stack = [] # 存 x - min_val
self.min_val = 0
def push(self, val: int) -> None:
if not self.stack:
self.min_val = val
self.stack.append(0)
else:
self.stack.append(val - self.min_val)
if val < self.min_val:
self.min_val = val
def pop(self) -> None:
d = self.stack.pop()
if d < 0:
# 弹出的就是当时的最小值，恢复
self.min_val -= d
def top(self) -> int:
d = self.stack[-1]
return self.min_val + d if d >= 0 else self.min_val
def getMin(self) -> int:
return self.min_val复杂度分析
- 时间复杂度：所有操作 $O(1)$。
- 空间复杂度：$O(n)$，只用一个栈。
两种方法对比
| 方法 | 时间 | 空间 | 特点 |
|---|---|---|---|
| 辅助栈 | $O(1)$ | $O(n)$ | 思路最直观，代码最短，面试首选 |
| 单栈存差值 | $O(1)$ | $O(n)$ | 空间省一半，但逻辑绕，有溢出风险 |
推荐：
- 面试：先写辅助栈，思路清晰、代码简洁，面试官一眼能看懂；
- 进阶：可以提一下「单栈存差值」的思路，展示对空间优化的理解。
关键细节
1. 为什么辅助栈能同步弹出
辅助栈和元素栈长度始终相同，且「辅助栈的第 i 个元素」就是「元素栈前 i 个元素中的最小值」。因此：
- 元素栈压入时，辅助栈也压入；
- 元素栈弹出时，辅助栈也弹出；
- 元素栈栈顶时，辅助栈栈顶就是当前最小值。
两者一一对应，永远不会错位。
2. 用 math.inf 做哨兵的技巧
self.min_stack = [math.inf]在辅助栈底部放一个 inf，好处是 push 时不需要特判空栈：
self.min_stack.append(min(val, self.min_stack[-1]))否则要写：
if not self.min_stack:
self.min_stack.append(val)
else:
self.min_stack.append(min(val, self.min_stack[-1]))用一个哨兵，代码干净很多。
3. 单栈差值法的还原公式
为什么弹出负差值时 min_val -= d？
设当前最小值为 min_val，压入的新元素 x < min_val，压入的差值为 d = x - min_val < 0。
弹出时，我们要把 min_val 恢复为 x：
所以 min_val -= d。
总结
- 核心观察：栈是后进先出，只要
a在栈里，a入栈时的「历史最小值」就是当前栈内最小值； - 辅助栈：与元素栈同步增删，每个位置存「到该位置为止的最小值」；
- 关键操作：
push：辅助栈压入min(x, min_stack[-1])；pop：两栈同步弹出；getMin：返回辅助栈栈顶；
- 哨兵技巧：辅助栈底部放
math.inf，省掉空栈判断； - 进阶思路：单栈存差值，空间省一半，但有溢出风险。
相关题目
- LC 716. 最大栈（要求同时支持最大值的栈）
- LC 剑指 Offer 30. 包含 min 函数的栈（本题的简化版本）