最小栈从原理到实现：辅助栈与O(1)差值法全解析

昨天帮一个朋友看力扣刷题进度他卡在 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 3push 5 后[3, 5]min 还是 3push 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) 的如果真追求极致还有下面的差值法。维度同步版不同步版辅助栈长度始终与数据栈相等最多与数据栈相等通常更短pop 逻辑无条件同步弹出需要判断后再弹正确性风险低逻辑直观中判断顺序容易写错平均空间O(n)最好 O(1)最坏仍 O(n)适用场景面试首选工程可读性好对空间敏感时使用2.4 用一组数据完整走一遍文本讲解再多不如实际跑一遍数据。假设依次执行以下操作push(3) push(5) push(2) push(-1) push(4) pop() getMin()每一步两个栈的内容是这样的操作stackmin_stackgetMin 返回值push(3)[3][3]3push(5)[3, 5][3, 3]3push(2)[3, 5, 2][3, 3, 2]2push(-1)[3, 5, 2, -1][3, 3, 2, -1]-1push(4)[3, 5, 2, -1, 4][3, 3, 2, -1, -1]-1pop()[3, 5, 2, -1][3, 3, 2, -1]-1getMin()[3, 5, 2, -1][3, 3, 2, -1]-1注意看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 或 Javaint溢出问题必须处理。举个例子val 2_000_000_000min_val -2_000_000_000两者之差是4_000_000_000直接超出 32 位有符号整数范围。怎么办在 C 里用long long存diffJava 里用long存。如果你在面试时主动提到这一点面试官通常会对你另眼相看因为这体现的不只是会背题而是真的理解边界条件。初始化min_val时我用的是float(inf)配合not self.stack判断可以避免第一次入栈时比较出错。另一种写法是把第一个入栈值直接设为min_val然后压入diff 0逻辑也是一样的。3.4 差值法的实测验证用同样的数据走一遍依次 push 3、5、2、-1、4。初始stack []min_val infpush(3)栈空压入 0min_val 3。stack [0]push(5)diff 5 - 3 2压入 2min_val 不变。stack [0, 2]push(2)diff 2 - 3 -1压入 -1min_val 更新为 2。stack [0, 2, -1]push(-1)diff -1 - 2 -3压入 -3min_val 更新为 -1。stack [0, 2, -1, -3]push(4)diff 4 - (-1) 5压入 5min_val 不变。stack [0, 2, -1, -3, 5]pop()弹出 5diff 0min_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 2push(2)getMin 2pop()getMin 2push(-1)getMin -1pop()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(fstep {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 里占一个位置就是因为它麻雀虽小五脏俱全数据结构设计、历史状态保存、边界条件处理、空间与时间的权衡一个都没少。把这些点吃透比单纯记住代码有意义得多。最后再分享一个我在实际刷题中的体会最小栈这类题目第一遍做的时候最好亲手把每一步两个栈的内容画出来别只盯着代码看。画过一遍之后你对为什么辅助栈要这样同步的理解会深很多。后面再遇到类似需要记录历史状态的题比如带括号的表达式求值、函数调用栈的深度统计你都会下意识地想到这个套路。