155. 最小栈 (Medium)
专题归类： 06-栈与堆 · 12-技巧专题 LeetCode 链接： https://leetcode.cn/problems/min-stack/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
设计一个支持 push、pop、top 操作，并能在 常数时间 内检索到最小元素的栈。
实现 MinStack 类：
MinStack()初始化堆栈对象。void push(int val)将元素 val 推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
示例：
输入：
["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，最多调用 3×10^4 次操作。所有操作都在非空栈上调用（pop/top/getMin 不会在空栈时调用）。
- 输入输出特征： 设计题，需要自行管理内部数据结构。核心要求是 getMin 必须是 O(1) 时间。
- 边界条件： 栈空时不会调用 pop/top/getMin，所以不需要处理这些异常情况。push 时 val 可能很大（int 范围）。
- 核心约束： getMin 必须 O(1)。简单思路是每次 getMin 遍历整个栈，但那样是 O(n)，不符合要求。
- 隐藏条件：
- 需要保持栈的 LIFO 特性不变（push 和 pop 行为与普通栈一致）。
- 多个相同最小值的情况如何处理？比如 push(1), push(1)，pop 一次后最小值仍然是 1。
- 最小值可能随着 pop 操作而改变（如果当前最小值被 pop 掉了，新的最小值应该是次小值）。
小白版直白理解
就像你在管理一个 书架，随时要知道书架里最矮的那本书有多高。
普通的做法是：每次你想知道最矮的书，就把所有书拿出来量一遍（O(n)）。但这太慢了。
聪明做法是 准备一个小本本：每次放新书上去的时候，把小本本上的最矮高度和新书高度比较，把更矮的那个记下来。这样任何时候你都能立刻知道最矮的书有多高。
这个”小本本”就是 辅助栈：它的栈顶永远记录着当前数据栈中的最小值。
解题思路
思路一：辅助栈（推荐）
核心思想： 使用两个栈：数据栈正常存储所有元素，辅助栈同步存储当前栈中的最小值。每次 push 时，辅助栈 push min(val, 辅助栈栈顶)；每次 pop 时两个栈同时 pop。
为什么辅助栈能记录最小值？因为栈是 LIFO 结构，辅助栈与数据栈同步操作，辅助栈的第 i 个元素就对应数据栈前 i 个元素中的最小值。
class MinStack:
def __init__(self):
self.stack = [] # 普通数据栈
self.min_stack = [float('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)
思路二：单栈 + 差值法（空间优化）
核心思想： 用一个栈存储当前值与当前最小值的差值，同时用一个变量维护当前最小值。push 时：如果栈为空，最小值设为 val；否则计算差值 diff = val - min_val 入栈，如果 diff < 0 说明 val 是新的最小值，更新 min_val。pop 时：如果栈顶差值为负，说明当前最小值需要还原为上一个最小值。
class MinStack:
def __init__(self):
self.stack = [] # 存储差值
self.min_val = 0
def push(self, val: int) -> None:
if not self.stack:
self.min_val = val
self.stack.append(0)
else:
diff = val - self.min_val
self.stack.append(diff)
if diff < 0:
self.min_val = val # 更新最小值
def pop(self) -> None:
if self.stack:
diff = self.stack.pop()
if diff < 0:
self.min_val = self.min_val - diff # 恢复上一个最小值
def top(self) -> int:
diff = self.stack[-1]
if diff < 0:
return self.min_val
return self.min_val + diff
def getMin(self) -> int:
return self.min_val复杂度： 所有操作 O(1)，空间 O(n)（但节省了一个栈的空间，实际约省一半）。
注意： 差值法可能面临整数溢出问题（val - min_val 可能超出 int 范围），在实际工程中使用辅助栈更安全。
易错点
- 辅助栈的初始值： 辅助栈的第一个元素（对应数据栈为空时）应该设为
inf或极大值，使得第一次 push 时min(val, inf)结果为 val。如果初始化为 0，当 val > 0 时最小值会错误地变成 0。 - 辅助栈同步操作： pop 时必须两个栈同时 pop，否则辅助栈栈顶不再对应当前数据栈的最小值。常见的 bug 是数据栈 pop 了但忘记 pop 辅助栈。
- 重复最小值： 当 push(1), push(1) 时，辅助栈中会存储两个 1。pop 一个后，辅助栈栈顶仍然是 1，最小值不变。这是正确的行为。
- 差值法的整数溢出： Python 不会溢出（大整数），但其他语言（C++/Java）中
val - min_val可能溢出 int 范围。 - getMin 在空栈时： 题目保证不会在空栈时调用，但实际工程中需要处理。
框架提炼
辅助栈模板：
class MinStack:
def __init__(self):
self.main_stack = []
self.helper_stack = [float('inf')]
def push(self, val):
self.main_stack.append(val)
self.helper_stack.append(min(val, self.helper_stack[-1]))
def pop(self):
self.main_stack.pop()
self.helper_stack.pop()
def top(self):
return self.main_stack[-1]
def getMin(self):
return self.helper_stack[-1]扩展思路： 这种「辅助数据结构」的思路不仅用于最小栈，还可以用在其他需要在 O(1) 时间内获取栈中最大元素的场景（最大栈：辅助栈存 max 即可）。
关联题目
- 20-有效的括号 — 栈的基础应用，与最小栈共用栈的基本操作（push/pop/peek），但 20 没有辅助结构。
- 295-数据流的中位数 — 双堆技巧维护中位数，与最小栈的双栈思路异曲同工：都是利用额外数据结构在 O(1) 时间获取特定统计量。
- 716-最大栈 — 最小栈的镜像问题，需要同时支持 getMax 操作，解法完全相同（辅助栈存 max 代替 min）。