今天想聊聊最小栈这道题。很多人刷到它的时候第一反应是“这不就是个栈吗”但真正写起来才发现getMin()的 O(1) 要求把大家从 O(N) 的舒适区里硬生生拽了出来。这道题几乎出现在每一本算法面试题库里LeetCode 上叫 Min Stack剑指 Offer 里叫包含 min 函数的栈核心就一句话设计一个栈支持push、pop、top、getMin四个操作并且getMin要在常数时间内返回栈内最小值。看起来简单但它的价值不在于“能不能写出来”而在于“能不能从 O(N) 走到 O(1)”。这篇文章会把从暴力解到辅助栈、再到差值法的完整进化路线拆开讲配合可直接运行的代码、边界测试用例和我在实际面试中踩过的坑。无论是准备面试的初学者还是想系统梳理栈类题目套路的开发者都能从这里拿到一点东西。1. 先看清题目在考什么从暴力解到真正的需求1.1 题目本来的样子原题描述很短大概是这样设计一个支持push(val)、pop()、top()和getMin()的栈结构要求getMin()的时间复杂度为 O(1)。注意这里有个隐藏前提push、pop、top本身是栈的基本操作O(1) 是理所当然的所以真正被“限时”的只有getMin()。这就意味着你不能在调用getMin()的时候再去遍历整个栈也不能用一个全局变量简单记录最小值因为一旦执行pop()全局最小值可能已经被弹出你根本不知道剩下的元素里的最小值是多少。很多人第一次看到这道题会想那我用一个变量存最小值不就行了吗push的时候更新它getMin()直接返回它。但问题马上出现在pop上——如果弹出的恰好是这个最小值你需要重新找到当前栈里的最小值这一步如果不提前做预处理就不可避免地要遍历剩余元素时间复杂度就回到了 O(N)。所以这道题真正考的不是“能不能想到存一个最小值”而是“你能不能想到把每个时刻的最小值历史都保存下来”。1.2 暴力解其实没有错只是不够优雅先写一个最直观的版本用数组模拟栈getMin()时遍历整个栈class MinStack: def __init__(self): self.data [] def push(self, val: int) - None: self.data.append(val) def pop(self) - None: self.data.pop() def top(self) - int: return self.data[-1] def getMin(self) - int: return min(self.data)这段代码完全符合题目的功能要求所有操作都能正确返回结果。但getMin()是 O(N) 的每次都要对整个栈做一次线性扫描。在面试场景里如果面试官先让你实现一个能跑的版本这个答案是可以的但如果你止步于此基本就拿不到这道题的加分项了。我见过不少候选人在这里卡住不是因为不会写min()而是因为他们默认了“栈已经是 O(1) 了getMin()花点时间也没什么”。但卖点恰恰在于getMin()会被频繁调用如果每次都是 O(N)那在一个大量读最小值的场景下整体复杂度就被拖垮了。比如你实现一个历史价格监控系统数据源源不断入栈而查询“当前最低价”的频率可能比push还高这时候一个 O(N) 的查询意味着系统响应时间随数据量线性增长这显然是不可接受的。所以暴力解的意义在于先确保功能正确再思考如何优化。这是很典型的算法思维第一步——不要一上来就想着最优解先把问题做对再一步步压缩复杂度。2. 辅助栈空间换时间的经典入门思路2.1 核心思路与为什么能 O(1)既然问题出在“弹出最小值之后不知道下一个最小值是谁”那最直接的解决办法就是把每一次push之后栈内的最小值都记下来pop的时候同步扔掉对应的记录这样getMin()就永远只需要看当前记录的最上面一项。这需要一个辅助栈我习惯叫它min_stack。它的长度始终和数据栈保持一致第 i 项表示“数据栈前 i 个元素中的最小值”。用文字描述可能有点绕直接看代码class MinStack: def __init__(self): self.data [] self.min_stack [] def push(self, val: int) - None: self.data.append(val) if not self.min_stack or val self.min_stack[-1]: self.min_stack.append(val) else: self.min_stack.append(self.min_stack[-1]) def pop(self) - None: self.data.pop() self.min_stack.pop() def top(self) - int: return self.data[-1] def getMin(self) - int: return self.min_stack[-1]每次push的时候把“当前值”和“辅助栈顶历史最小值”做比较较小的那个压入辅助栈。这相当于给数据栈的每个元素都配了一个“当时的最小值快照”。数据栈弹出的时候辅助栈也同步弹出因为栈的结构保证我们永远只需要关心栈顶的局部状态之前的历史最小值已经按顺序记录在辅助栈下层了。2.2 一个容易踩的坑pop 时一定要同步回退很多第一次写辅助栈的人会犯一个错只在push时更新辅助栈而pop的时候忘了把辅助栈也弹出去。比如这样def pop(self) - None: self.data.pop()看起来好像没什么问题但如果你在push的时候用了“小于等于才压入”的策略那么辅助栈里记录的其实是“历史最小值序列”。一个典型场景依次 push 5、3、8辅助栈记录 5、3、3。执行 pop 弹出 8辅助栈仍然停在 3 上没问题。再执行 pop 弹出 3辅助栈还是 3问题来了——数据栈现在只剩下 5真实最小值应该是 5但getMin()返回的却是 3。这就是为什么pop时数据栈和辅助栈必须同步弹出。算法题写到后面往往不是难在思路而是难在这些“看起来理所当然”的同步逻辑。不少提交在 LeetCode 上报错原因都出在这里。2.3 复杂度分析与适用场景这个版本的时间复杂度是 O(1)所有操作都只访问栈顶不涉及遍历。空间复杂度是 O(N)因为辅助栈长度和数据栈一致。在面试里这是一个标准的可接受答案在 LeetCode 上能直接 AC。但它有没有可以压缩的空间有。辅助栈的最大问题在于即使当前元素不是新的最小值我们也会把“旧最小值”再复制一份压进去这在最坏情况下会浪费大量空间。如果你 push 的数据是严格递增的辅助栈里存的就全都是第一个元素的值比如连续 push 1、2、3、4、5 一万次辅助栈就存了一万个 1。这时候你可能会想如果辅助栈只在出现新最小值时才增长空间不是能省很多吗这就是另一个常见的变体辅助栈只在val min_stack[-1]时才压入pop时如果弹出的元素恰好等于辅助栈顶再做同步弹出。这个版本在数据递增时辅助栈几乎不长但代码要多写一个“弹出的元素是否等于当前最小值”的判断。我个人的经验是这个压缩版的代码稍难懂面试时容易说漏所以除非面试官明确问“能不能优化空间”我更推荐每一层都记录快照的版本逻辑清楚不容易写错。3. 差值法把辅助空间的常数摊掉3.1 核心原理栈里存 diff 而不是真值如果你在面试中写完了辅助栈面试官大概率会追问一句“空间还能不能更省”这时候就到了差值法出场的时候。差值法的核心思想非常巧妙栈里不再存原始值而是存“当前值和当前最小值之间的差值”。同时维护一个全局变量min_val表示当前栈内的最小值。getMin()直接返回min_val不需要额外空间push、pop、top通过栈顶存的正负 diff 来判断如何更新和维护min_val。说得更具体一点栈顶元素存的是diff val - min_val。如果diff 0说明当前值不小于最小值最小值不需要更新如果diff 0说明当前值比已知最小值还小这时候需要把min_val更新为val。这里的关键点在于当diff 0时val本身就被编码在了 diff 和min_val的关系里。因为diff val - 旧 min_val而旧 min_val 就是压入这个元素之前的最小值所以当你知道了 diff 和新 min_val 之后可以反推出当时的旧 min_val。3.2 push / pop / top 的三种分支判断直接看代码我加了详细注释class MinStack: def __init__(self): self.stack [] self.min_val 0 def push(self, val: int) - None: if not self.stack: # 第一个元素栈空直接建立基准 self.stack.append(0) self.min_val val else: 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: # 当前栈顶对应的真实值就是 diff min_val return diff self.min_val else: # 栈顶元素是历史最小值真实值就是它本身 return self.min_val def getMin(self) - int: return self.min_val这段代码的妙处在于空间复杂度从 O(N) 降到了 O(1)因为除了栈本身我们只多维护了一个min_val变量。代价是每次push、pop、top都要做符号判断逻辑比辅助栈复杂一些。我拆开讲一遍执行流程确保大家能真正理解而不是背代码假设依次 push 3、5、2。push(3)栈空压入 0min_val 3。此时栈内元素含义3。push(5)diff 5 - 3 2压入 2。因为 2 0min_val不变仍为 3。此时栈内元素含义3、5。push(2)diff 2 - 3 -1压入 -1。因为 -1 0更新min_val 2。此时栈内元素含义3、5、2。现在执行 pop()栈顶 diff -1说明它对应的是当时的新低 2。min_val min_val - (-1) 2 1 3正好回退到上一个最小值。数据栈弹出后剩下 3、5。再来执行 top()栈顶 diff 2真实值 diff min_val 2 3 5正确。这就是差值法的完整逻辑diff 0的栈顶元素其真实值就是min_valdiff 0的栈顶元素其真实值等于diff min_val。pop时也只有当栈顶 diff 为负时才需要回退min_val因为只有负 diff 才意味着最小值发生了变化。3.3 为什么实际工程中不常用差值法在面试里是个亮眼的优化方案但在真实工程里我几乎不会用原因有两个。第一是边界条件容易错。比如很多语言的 int 类型是 32 位有符号整数当val很大而min_val很小的时候diff val - min_val可能会溢出。LeetCode 上这道题的默认环境是 PythonPython 的 int 是任意精度所以不会暴露这个问题但在 C 或 Java 里你需要把 diff 声明成long long否则就会在极端测试用例上翻车。我记得有段时间 LeetCode 新增了一些大数用例不少用差值法提交的 C 代码直接溢出报错改成长整型才通过。第二是代码可读性差。一个维护 diff 的栈对后期维护的人非常不友好。你看到栈里存着 -1、2、0 这样的数字完全不知道原始值是什么。一旦有人不小心改了min_val的逻辑bug 会非常隐蔽。辅助栈方案虽然多费点空间但栈里存什么一目了然可维护性高得多。所以我的建议是面试时可以讲差值法展示你懂优化但如果是写生产代码我默认选辅助栈。4. 节点内嵌 min比辅助栈更直观的变体4.1 思路与代码除了辅助栈还有一个不少人喜欢用的变体不用两个栈而是把“当前最小值”作为字段存进每个栈节点里。说得直白点就是让每个元素除了自己的值还带一个“压入它时整个栈的最小值”快照。class MinStack: class Node: def __init__(self, val: int, min_val: int): self.val val self.min_val min_val self.next None def __init__(self): self.head None def push(self, val: int) - None: if self.head is None: self.head self.Node(val, val) else: node self.Node(val, min(val, self.head.min_val)) node.next self.head self.head node def pop(self) - None: self.head self.head.next def top(self) - int: return self.head.val def getMin(self) - int: return self.head.min_val这个版本的本质和辅助栈一模一样都是空间换时间只不过把辅助栈的“同步记录”变成了嵌入式字段。它的好处在于不需要维护两个栈的长度同步pop时不会出现辅助栈和数据栈不一致的问题因为信息和节点绑定在一起结构上天然安全。但它的缺点也很明显每个节点多存一个min_val字段内存开销比辅助栈更大。因为辅助栈存的是 int而节点不但存字段还有对象头、引用指针等额外开销。在 Python 里这个差距尤其明显一个 Node 实例的内存占用远远大于两个整数列表项。所以我很少在生产代码中这样写一般只在写链表题或面试时作为方案讨论。4.2 几种方案的横向对比简单做个总结方便你面试时快速选择合适的方案方案核心思想时间复杂度空间复杂度代码复杂度推荐场景暴力遍历getMin 时遍历栈O(N)O(N)极低功能验证非面试答案辅助栈每层记录每个元素存当时最小值快照O(1)O(N)低面试标准答案生产首选辅助栈稀疏记录只在最小值变化时入栈O(1)最坏 O(N)常数小中空间敏感或递增数据多差值法栈存 diff全局维护 minO(1)O(1)高面试展示优化能力节点内嵌 min每个节点存最小值和 nextO(1)O(N)常数大低链表场景或练习从这张表能看出一个规律所有 O(1) 的getMin方案本质上都在做同一件事——把“查询时需要的计算”提前到“push 时完成”也就是用预计算换取查询速度。这是典型的空间换时间思维也是这类题目的核心考点。5. 手写测试用例把边界情况一次打穿5.1 典型边界场景写完代码之后最忌讳的就是直接提交。我自己刷题的习惯是先手写一批测试用例把常见的坑全部踩一遍再上去交。针对最小栈下面这些场景必须覆盖第一个是空栈操作。有些语言里getMin()定义在空栈上行为未定义但你要确保自己的实现不会崩。Python 里直接self.min_stack[-1]会报 IndexError所以题目一般会保证不会对空栈调用getMin()和pop()但你自己测试时还是要留意。第二个是递减序列。依次 push 5、4、3、2、1每次getMin()都要返回当前栈顶位置对应的最小值。递减序列是辅助栈最容易暴露问题的地方因为每一个元素都是新低辅助栈会一路增长。第三个是递增序列。依次 push 1、2、3、4、5getMin()始终返回 1。递增序列对稀疏辅助栈方案是个福音空间占用非常小但如果你用的“每层记录”版本空间会线性增长没有任何优化空间。第四个是重复最小值。比如依次 push 2、2、2、2然后pop两次getMin()仍然应该返回 2。很多人在重复值上翻车因为他们在push时用了val min_stack[-1]严格小于而不是导致重复最小值没有被正确记录pop掉一个 2 之后辅助栈顶变成了一个更大的数getMin()就错了。我建议每个想彻底掌握这道题的人都花两分钟手动跑一遍下面这个测试用例stack MinStack() stack.push(3) stack.push(5) assert stack.getMin() 3 stack.push(2) stack.push(2) assert stack.getMin() 2 stack.pop() assert stack.getMin() 2 stack.pop() assert stack.getMin() 3 stack.push(-1) assert stack.getMin() -1如果这套用例能一次通过说明你对最小栈的理解已经合格了。5.2 常见问题与排查技巧实录我在实际调试这道题时遇到的最高频问题整理成一张速查表方便你对照排查现象可能原因解决方案getMin 返回错误值push 时没同步更新辅助栈检查压栈逻辑每层都要记录快照pop 后 getMin 变错pop 时漏了同步弹出辅助栈在数据栈 pop 的同时 pop 辅助栈重复最小值处理错误push 时用而不是判断新值等于最小值时也要压入辅助栈或压入的是旧 min 而非 val差值法返回负数或异常大数int 溢出将 diff 声明为 long long 或改用辅助栈top 返回错误真实值差值法分支判断写反记住 diff 0 时真实值就是 min_val对象初始化报错在init里忘记初始化 min_stack每次创建对象都要重新初始化数据结构这里我特别想提一个细节push时辅助栈压入判断。如果你选择“每层记录”版本if not self.min_stack or val self.min_stack[-1]和else: append(self.min_stack[-1])是等价的但在面试时写成一简一繁的 if-else 有风险。我更推荐写成if not self.min_stack: self.min_stack.append(val) else: self.min_stack.append(min(val, self.min_stack[-1]))这样逻辑更直白不用纠结符号也不会在重复值上犯错。6. 面试题背后真正的算法思维6.1 从“能否实现”到“能否更好”的进阶最小栈这道题从 O(N) 到 O(1) 的进化其实映射了算法思维里一条很重要的主线不做重复计算把开销前置。暴力解的浪费在于每次getMin()都把整个栈扫一遍但很多扫描是完全重复的——前一个状态的最小值和后一个状态的最小值之间有大量重叠信息。辅助栈做的事很朴素把每一次查询想得到的答案在写入时就已经算好存起来。这就是“预计算”思维它贯穿了整个算法设计。差值法看上去更炫但它真正的意义不在“节省空间”而在于展示你能不能用数学关系编码信息。栈里存的不再是数据本身而是数据与状态的差值通过一个全局变量作为“参照物”就能完整还原所有原始数据。这是一种更高级的思维当结构无法直接满足需求时改变存储的语义。面试官真正想看的往往不是某一种具体解法而是你在面对“标准数据结构无法满足新需求”时如何分析、取舍、迭代。所以这道题在面试中的正确节奏应该是先用暴力解保证正确性。再提出辅助栈方案讲清楚空间换时间的本质。如果被追问再展示差值法并主动指出它的溢出风险和可读性问题。这样一套组合拳下来既展现了扎实的编码能力又体现了工程权衡意识比闷头写出一个最优解给人的印象好得多。6.2 这道题能迁移到哪些场景最小栈的思路不止能解这一道题。只要你需要“在动态增删的数据结构中快速查询某个统计量”空间换时间 预计算的思想都能派上用场。最直接的是最小队列设计一个队列支持push、pop、getMin都是 O(1)。这比最小栈难因为队列是先进先出你不能只靠一个辅助栈维护。主流解法是用两个栈模拟队列再叠加最小栈的思想。本质上还是“把状态分阶段记录”。再延伸一下单调栈算法其实也是同一个思维脉络维护一个额外的单调递减或递增栈用来快速获取当前区间的最值信息。比如接雨水、柱状图中最大的矩形核心都是在遍历过程中维护一个单调结构避免重复扫描。如果你对算法的认识只停留在“会做这道题”那最小栈也就只是一道题如果你能从这道题里提炼出“预计算避免重复查询”“用辅助结构记录中间状态”这些通用套路它就能帮助你在更多题目里打开思路。我个人刷题的经验是遇到一道好题值得花时间把它从暴力解到最优解的每一步都想明白远比一天刷十道题有价值。最后说点实际的我在面试别人的时候通常不看候选人能不能写出最终版本而是看他怎么描述自己的思考过程。能直接写出辅助栈的人不少但能主动说出“这个方案空间复杂度是 O(N)如果数据量很大可能是个瓶颈还可以用差值法压到 O(1)”的人寥寥无几。这道题真正的分水岭就在于你有没有对复杂度做主动的、体系化的思考。你如果能把这一点练成习惯那收获的可就不只是这一道题的 AC 了。