昨天帮一个朋友看力扣刷题进度，他卡在 hot100 里的第 155 题最小栈，说这题标签写着"简单"，但提交时总是有测试用例过不了。我扫了一眼他的代码，第一眼就猜到问题出在哪：他给栈配了一个全局 min 变量，push 的时候顺手更新最小值，等到 pop 把最小元素弹出去，这个 min 就再也回不来了。这题表面考栈，实际考的是"历史状态的回溯"，而大部分第一次做的人都会栽在同一个地方。这篇文章我打算把最小栈从原理到实现完整拆一遍，包括辅助栈、常数空间差值法、边界条件调试，以及面试官通常会追问的变体。无论你是刚开始刷题的初学者，还是准备面试想冲刺的人，应该都能从里面找到直接能用的东西。

1. 这道题真正的坑点：为什么不能只存一个 min 变量

1.1 站在出题人的角度重新读题

题目本身不复杂：设计一个支持push、pop、top、getMin操作的栈结构，要求这四种操作的时间复杂度都是 O(1)。

push、pop、top本来就是栈的标配能力，数组或者链表随便实现都是常数时间。真正有含金量的是最后这个getMin()：在任意时刻，快速拿到当前栈里的最小值。

如果让你先不想任何约束，最暴力的做法是什么？getMin()的时候把整个栈遍历一遍，找出最小值。这个能过吗？能过功能测试，但时间复杂度是 O(n)，数据量一大就会超时，这明显不是出题人想要的。

那换个思路：既然每次都遍历太慢，我能不能用一个变量把当前最小值缓存起来？push的时候如果新值更小就更新这个变量，getMin()直接返回它。听起来完美解决，时间复杂度也确实是 O(1)。这个方案就是大多数人踩的第一个坑。

1.2 全局变量为什么失效：一个具体例子

我们走一组数据：依次push 3、push 5、push 2。

• 栈内元素：[3]，缓存 min = 3
• push 5 后：[3, 5]，min 还是 3
• push 2 后：[3, 5, 2]，min 更新为 2

现在做一个pop，弹出了栈顶的 2。栈变成 [3, 5]，此时真实的最小值是 3。但你的缓存 min 还是 2，而且没有任何机制能让它"回退"到上一个最小值。

问题就出在这里：最小值不是一个孤立的数字，它是依附于栈内容存在的。栈顶元素被弹出去之后，如果这个栈顶恰好是当前最小值，那么栈的"最小状态"就必须回到它入栈之前的样子。只存一个全局变量，相当于只保存了当前状态，没有保存历史状态。可栈的 pop 操作恰恰需要你根据历史来恢复现场。

1.3 本质：最小值和栈的状态强绑定

我们可以把问题看得更抽象一点：数据结构是 LIFO，后进先出。每一次 push，都是往当前状态上叠加一个新状态；每一次 pop，则是回退到上一个状态。这意味着"当前最小值"这个信息，严格来说应该是每个状态都有一份的。

如果用一个变量，它只能代表某一时刻的快照；而栈需要的是一整套"历史最小值序列"。就像是坐电梯，你想知道这栋楼每一层对应的最低楼层记录，就不能只记一个"当前最低楼层"，你得把每一层经过时的最低值都留档，不然电梯往下走的时候，记录就断掉了。

所以解题的关键，不是怎么优化那个变量，而是想清楚：怎么保存这份历史最小值档案。想明白了这一点，辅助栈的解法就呼之欲出了。

2. 辅助栈解法：用空间换来的"历史最小值档案"

2.1 设计思路

既然需要一个"历史最小值序列"，那最直接的办法就是用另一个栈来存它。

主栈正常存储所有元素，负责push、pop、top；辅助栈则专门记录"每一步操作后当前栈内的最小值"。具体来说：

• push(val)：主栈照常压入val；辅助栈压入一个值，这个值是min(val, 辅助栈当前栈顶)。
• pop()：主栈弹出，辅助栈同步弹出。
• top()：返回主栈栈顶。
• getMin()：返回辅助栈栈顶。

辅助栈的栈顶永远等于主栈在当前状态下的最小值，所以getMin()才能在 O(1) 时间内返回结果。这个方案的本质是空间换时间：多用一个栈，换来所有操作都是常数时间。

2.2 完整代码

用 Python 写起来非常干净：

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]

这段代码里有几个细节值得留意。

第一，辅助栈的push分支里，第一次入栈时需要单独判断min_stack是否为空。因为空栈没有栈顶，你不能拿min(val, 空)去比较。有些朋友喜欢把min_stack初始化为[float('inf')]，这样就不用写 if 分支了，也是一种常见写法，但会额外多一个永远不弹出的哨兵节点，逻辑上稍微脏一点，我更喜欢清晰的分支判断。

第二，同步版里两个栈的长度始终一致，所以pop()时可以放心地同时弹出。这种"同步"的感觉，就像两个人并排走路，步调完全一致，不容易出乱子。

2.3 同步版与不同步版怎么选

上面这种是同步版，辅助栈的元素个数始终和数据栈一样。还有一种不同步版：只在入栈元素小于等于当前最小值时，才把值压入辅助栈。比如：

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 or val <= self.min_stack[-1]: self.min_stack.append(val) def pop(self) -> None: if self.stack[-1] == self.min_stack[-1]: self.min_stack.pop() self.stack.pop() def top(self) -> int: return self.stack[-1] def getMin(self) -> int: return self.min_stack[-1]

两种写法的时间复杂度完全一样，空间上不同步版在很多时候更省。比如依次 push 5, 6, 7，同步版的辅助栈里存的是 [5, 5, 5]，不同步版辅助栈只有 [5]。但不同步版的pop()逻辑要小心：先判断当前弹出的元素是否等于辅助栈栈顶，如果相等，辅助栈才跟着弹出。

两版的取舍，我的建议很直接：面试写同步版。它的正确性一目了然，不需要动脑判断"什么时候该同步、什么时候不该同步"，出错的概率低很多。不同步版适合你已经非常熟练、想跟面试官展示你对空间利用有思考的情况。说到底，这题的空间复杂度最优是可以做到 O(1) 的，如果真追求极致，还有下面的差值法。

2.4 用一组数据完整走一遍

文本讲解再多，不如实际跑一遍数据。假设依次执行以下操作：

push(3) push(5) push(2) push(-1) push(4) pop() getMin()

每一步两个栈的内容是这样的：

注意看push(4)这一步：4 比当前最小值 -1 大，所以辅助栈压入的还是 -1。这正是同步版的核心：辅助栈不记录"新元素"，而是记录"当前全局最小值在每一步的延续"。这个设计保证了无论什么时候pop，辅助栈栈顶都能正确反映剩余数据栈的最小值。

3. 差值法：在 O(1) 空间里用数学技巧偷师

3.1 动机与基本原理

辅助栈解法绝大多数情况下都能通过面试，但它有一个软肋：额外空间是 O(n)。如果面试官追问一句"能不能不用额外栈做到 O(1) 空间"，你就需要拿出差值法了。

差值法的核心思想是：不直接存原始值，而是在栈里存"当前值减去当前最小值"的差值。用一个变量维护当前最小值，然后用数学关系把原始值反推出来。

这个思路有点像记账不记余额，只记"这个月比上个月多了多少"，到了月底再根据总额倒推。听着很绕，拆开看其实还好。

定义：入栈时，设当前要入栈的值为val，当前全局最小值为min_val，那么在数据栈里压入的不是val，而是diff = val - min_val。

根据diff的符号，我们可以判断出两种情况：

• 如果diff < 0，说明val < min_val，也就是说这个入栈元素刷新了最小值，新的min_val应该更新为val。
• 如果diff >= 0，说明val >= min_val，最小值没有变化。

此时数据栈里的每个元素都不是真实值，而是"相对差"。但只要我们有min_val，就能在需要的时候还原真实值。

3.2 每一步怎么维护

分别看四个操作：

push(val)：计算diff = val - min_val，把diff压栈。如果diff < 0，把min_val更新为val。

pop()：弹出栈顶的diff。如果diff < 0，说明被弹出去的这个元素就是当前的最小值，并且它入栈时更新过min_val。弹出去之后，min_val需要回退到它入栈之前的值。怎么回退？设旧最小值为old_min，新最小值为val = min_val，入栈时diff = val - old_min。所以old_min = val - diff = min_val - diff。注意这里的diff是负数，减负数等于加正数，回退值是比当前min_val更大的数。如果diff >= 0，说明弹出的不是最小元素，min_val保持不变。

top()：要还原栈顶元素对应的原始值val。看栈顶的diff：如果diff >= 0，说明这个元素不小于当时的min_val，原始值就是min_val + diff；如果diff < 0，说明这个元素入栈时就是新的最小值，而当前min_val恰巧就是它，所以原始值就是min_val。

getMin()：直接返回min_val。

3.3 代码实现与溢出分析

直接上代码：

class MinStack: def __init__(self): self.stack = [] self.min_val = float('inf') def push(self, val: int) -> None: if not self.stack: self.stack.append(0) self.min_val = val return diff = val - self.min_val self.stack.append(diff) if diff < 0: self.min_val = val def pop(self) -> None: 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

这段代码有个很关键的细节：Python 的 int 是任意精度的，不会溢出，所以val - self.min_val可以随便算。但如果换成 C++ 或 Java，int溢出问题必须处理。

举个例子，val = 2_000_000_000，min_val = -2_000_000_000，两者之差是4_000_000_000，直接超出 32 位有符号整数范围。怎么办？在 C++ 里用long long存diff，Java 里用long存。如果你在面试时主动提到这一点，面试官通常会对你另眼相看，因为这体现的不只是会背题，而是真的理解边界条件。

初始化min_val时我用的是float('inf')，配合not self.stack判断可以避免第一次入栈时比较出错。另一种写法是把第一个入栈值直接设为min_val，然后压入diff = 0，逻辑也是一样的。

3.4 差值法的实测验证

用同样的数据走一遍：依次 push 3、5、2、-1、4。

初始：stack = []，min_val = inf

• push(3)：栈空，压入 0，min_val = 3。stack = [0]
• push(5)：diff = 5 - 3 = 2，压入 2，min_val 不变。stack = [0, 2]
• push(2)：diff = 2 - 3 = -1，压入 -1，min_val 更新为 2。stack = [0, 2, -1]
• push(-1)：diff = -1 - 2 = -3，压入 -3，min_val 更新为 -1。stack = [0, 2, -1, -3]
• push(4)：diff = 4 - (-1) = 5，压入 5，min_val 不变。stack = [0, 2, -1, -3, 5]
• pop()：弹出 5，diff >= 0，min_val 不变。-1 仍然正确
• top()：栈顶 diff = -3，小于 0，说明栈顶原始值就是当前 min_val = -1

数据全对得上。这个方案最妙的地方在于，数据栈里存的负数 diff 本身就是"发生过最小值更新"的标记，不需要额外字段。

3.5 生产环境的选择建议

差值法虽然空间上很有优势，但我不建议在真实的工程代码里用它。原因很简单：可读性太差了。几个月后你自己回来看这段代码，都得在草稿纸上推半天才能想起来min_val - diff是什么意思。而辅助栈方案，新同事扫一眼就能看懂。

我的建议是：面试时先给辅助栈方案，如果面试官追问空间优化，再讲差值法。这符合正常的思维过程：先有一个正确方案，再逐步优化。你上来就甩差值法，反而容易让人觉得你在背题。

4. 边界情况与实测调试：重复元素、空栈与溢出陷阱

4.1 重复元素是重灾区

这道题最容易写错的地方就是重复元素。很多人用不同步版辅助栈时，入栈判断写成if not min_stack or val < min_stack[-1]，也就是只在严格小于的时候才压入辅助栈。这在大多数测试用例下都能通过，直到遇到这个场景：

push(2) push(2) pop() getMin()

两个 2 入栈，辅助栈只记了一个 2。第一次 pop 时，栈顶 2 等于辅助栈栈顶 2，辅助栈弹出，此时辅助栈空了。但数据栈里还有一个 2，真实最小值仍然是 2。这时候调用getMin()，辅助栈为空，直接数组越界或者返回错误结果。

问题的根源是：两个相同的最小值，其中一个还没出栈，它的"最小值身份"不能提前注销。解决办法就是比较时用<=而不是<，保证每个相同的最小值都在辅助栈里有一个对应记录。同步版不存在这个问题，因为它无条件同步。

4.2 空栈与 pop 顺序

题目里通常会保证调用pop、top、getMin时栈非空，但你自己实现的时候还是要想想空栈的情况。

不同步版pop()的判断顺序尤其容易错：

# 错误写法：先 pop 数据栈，再比较 def pop(self): self.stack.pop() if self.stack[-1] == self.min_stack[-1]: self.min_stack.pop()

这里 pop 完之后self.stack[-1]已经变成新的栈顶了，和辅助栈栈顶比较的是值就不对了，甚至可能越界。正确写法是先比较、再弹出：

def pop(self): if self.stack[-1] == self.min_stack[-1]: self.min_stack.pop() self.stack.pop()

4.3 负数与初始化问题

有些同学初始化min_val为 0 或者None，然后在push里做比较，遇到负数就出问题。比如min_val = 0，你 push -5，-5 < 0，更新 min_val = -5，没问题。但如果先 push 3，再 push -5，第一次比较的时候3 < 0不成立，min_val 还是 0，就错了。

所以在初始化的处理上，要么用哨兵值float('inf')，要么用专门的标志位区分"栈是否为空"。这里没有捷径，就是用栈空判断兜底。

4.4 调试方法与实测过程

我在本地刷题时习惯写一个小驱动脚本，把操作序列打印出来，每一步都输出两个栈的内容。这个方法特别适合排查最小栈这类问题。

举个例子，用下面这个测试序列：

push(2), push(2), pop(), push(-1), getMin(), pop(), getMin()

预期结果是：

• push(2)：getMin = 2
• push(2)：getMin = 2
• pop()：getMin = 2
• push(-1)：getMin = -1
• pop()：getMin = 2

如果你用的是<而非<=，在第三步pop()之后辅助栈就空了，getMin()直接崩。这种错误光看代码很难发现，但把每一步的辅助栈内容打印出来，一眼就暴露了。

我的调试脚本长这样：

def debug(ops, values): ms = MinStack() for i, op in enumerate(zip(ops, values)): if op[0] == 'push': ms.push(op[1]) elif op[0] == 'pop': ms.pop() elif op[0] == 'top': print(ms.top()) elif op[0] == 'getMin': print(ms.getMin()) print(f'step {i}: stack={ms.stack}, min_stack={ms.min_stack}')

这种打印式调试虽然朴素，但确实能帮你快速定位是push分支写错还是pop分支写错。刷题阶段不需要引入什么调试器，print 就够了。

5. 从最小栈延伸出去：面试追问与相关变体

5.1 最大栈只改一个符号

最小栈的代码改成最大栈非常简单：同步版辅助栈里min改成max，判断符号反过来即可。真正值得注意的是一道更强的变体：同一时间既能取最小值又能取最大值。实现上就是一个栈加两个辅助栈，一个维护最小，一个维护最大。逻辑各自独立，互不干扰。

这类变体在面试里出现频率不低，因为出题人想确认你是理解了原理，而不是背了模板。你只需要说一句"辅助栈保存的其实是一个单调的前缀信息"，面试官通常就会点头。

5.2 节点携带最小值的做法

还有一种实现思路：把值和当时的最小值打包成一个节点。Python 里可以直接用元组：

class MinStack: def __init__(self): self.stack = [] def push(self, val: int) -> None: cur_min = val if not self.stack else min(val, self.stack[-1][1]) self.stack.append((val, cur_min)) def pop(self) -> None: self.stack.pop() def top(self) -> int: return self.stack[-1][0] def getMin(self) -> int: return self.stack[-1][1]

这段代码本质上是同步辅助栈的"合并版"：一个元组里同时存真实值和当前最小值。空间占用比双栈方案还省一点，因为不需要维护两个 list 的同步关系。缺点是每次压入的元素变大了（多了一个字段），在极端大数据的场景下内存占用反而可能更高。但作为面试的第二解，它很好讲清楚。

5.3 为什么不能用堆或者单调栈结构

有些朋友会问：getMin()不是求最小值吗？那我内部再用一个小顶堆存最小值行不行？

不行。堆的push和pop都是 O(log n) 的时间复杂度，不满足题目 O(1) 的要求。而且堆弹出的顺序和栈不一致：栈弹出的是栈顶元素，堆弹出的是最小值，两者状态会错位。这个方向从一开始就行不通。

单调栈也解决不了这个问题。单调栈维护的是"下一个更小/更大的元素"这类相对关系，而最小栈要求的是"当前全局最小值"。两者的信息维度不一样。

5.4 我面试时怎么考察这道题

作为面试官，我如果出这道题，重点不是看候选人能不能背出代码，而是看他怎么拆问题。第一步如果能想到"不能只存一个全局变量"，说明他对栈的状态变化有概念；第二步如果能说出辅助栈的同步/不同步区别，说明真的有实操过；第三步如果能在追问下给出差值法，并且主动提溢出问题，那这道题基本就可以给满分了。

这道题之所以在 hot100 里占一个位置，就是因为它麻雀虽小五脏俱全：数据结构设计、历史状态保存、边界条件处理、空间与时间的权衡，一个都没少。把这些点吃透，比单纯记住代码有意义得多。

最后再分享一个我在实际刷题中的体会：最小栈这类题目，第一遍做的时候最好亲手把每一步两个栈的内容画出来，别只盯着代码看。画过一遍之后，你对"为什么辅助栈要这样同步"的理解会深很多。后面再遇到类似需要"记录历史状态"的题，比如带括号的表达式求值、函数调用栈的深度统计，你都会下意识地想到这个套路。