1. 题目拆解与朴素解法为什么过不了关1.1 这道题到底在考什么很多第一次刷到「最小栈」的同学第一反应是“这不就是个栈吗我拿数组模拟一下再搞个变量存最小值不就完了”先别急题目里藏着真正的条件push、pop、top、getMin四个操作都要求O(1) 时间复杂度。这意味着你不能在getMin()的时候去遍历栈里剩下的元素找最小值——那一次调用就是O(n)题目限定的数据量一大直接超时。所以这道题表面考栈实际考的是你如何在每次元素进出的同时持续用一个可追踪、可恢复的数据结构维护“当前最小值”这个状态。换句话说getMin()之所以难不是因为“求最小值”本身难而是因为栈的pop操作会不断破坏你之前记录的最小值。你记录了一个全局变量min元素压进去的时候更新它很简单但一旦把最小值所在的元素弹出去你就再也回不到“上一个最小值”了。栈是后进先出的而最小值的历史状态必须跟着栈的弹出顺序一起“回退”。这就是整道题的核心矛盾。想明白这一点后面的解法思路就顺了。1.2 朴素思路的三个失败方案我在讲这道题的时候经常让读者先自己试着写出几种“看起来对但实际上不达标”的方案这个过程对理解题目帮助很大。第一种是遍历求最小值。push、pop都直接操作主栈getMin的时候临时遍历一遍栈内元素。功能上一点问题没有但getMin是O(n)。如果面试官让你分析复杂度这一关就过不去。第二种是只维护一个min变量。每次push的时候如果新元素更小就更新min。这个方案在“只压不弹”的场景下是对的可一旦执行pop并且弹出的正好是当前最小值你怎么办你根本不知道“上一个更小值”是多少。没有任何额外信息可以恢复min。所以这个方案只能通过极少数测试用例稍微构造一个“先压最小值再弹掉它”的用例立刻崩溃。第三种是每个节点存两个值节点里除了存当前元素还存“从栈底到当前位置的最小值”。这个思路其实已经非常接近正解了——它相当于把辅助栈的信息直接放进了每个节点里。空间复杂度同样是O(n)但实现起来每个Node要包一层对象代码略重。真正简洁的做法是把这部分“历史最小值”单独抽出来做成一个平行栈。关键认知题目要的“最小值”不是一个静态值而是一条与栈同步进退的历史曲线。任何做不到“同步回退”的方案都是伪 O(1)。2. 辅助栈解法空间换时间的最经典设计2.1 辅助栈的理论基础想通了核心矛盾之后解法也就呼之欲出了我再开一个栈专门存“每次压入之后当前栈内的最小值”。主栈每个时刻都有两个信息栈顶元素值以及“当前整个栈的最小值”。辅助栈就是在跟主栈完全同步地记录后者。来看细节push(x)主栈压入x。辅助栈的栈顶是当前最小值如果x比它小辅助栈压入x否则辅助栈再压入一次当前最小值。pop()主栈弹出辅助栈同步弹出。top()返回主栈栈顶。getMin()返回辅助栈栈顶。这个方案的关键点在于辅助栈的每一层都保存着主栈同一位深度时的最小值。哪怕主栈栈顶被弹走了辅助栈的栈顶也会跟着回退于是getMin天然就是 O(1)。为什么这个思路不容易出错因为它把“最小值的历史状态”和“元素的进出顺序”绑定在了一条时间线上。你不需要动任何脑子去“恢复现场”栈的弹出机制自己就帮你恢复了。2.2 辅助栈压缩写法只在更小值出现时压入上面说的“辅助栈每次都压入当前最小值”写起来很简单但有个小空间浪费——如果连续压入很多比当前最小值大的元素辅助栈会重复压入同一个最小值。比如压入[5, 6, 7, 8]辅助栈会变成[5, 5, 5, 5]全是冗余。所以更常见的写法是辅助栈只在“新元素小于等于当前最小值”时压入。弹出的时候如果主栈弹出的元素恰好等于辅助栈栈顶辅助栈才跟着弹。class MinStack { private DequeInteger stack; private DequeInteger minStack; public MinStack() { stack new ArrayDeque(); minStack new ArrayDeque(); } public void push(int val) { stack.push(val); if (minStack.isEmpty() || val minStack.peek()) { minStack.push(val); } } public void pop() { if (stack.pop().equals(minStack.peek())) { minStack.pop(); } } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); } }注意一个细节pop()比较的时候我用了equals而不是。这是因为Deque里的元素是Integer对象比较的是引用虽然小整数有缓存-128 到 127超过这个范围就出问题。刷题平台上的测试数字往往不大缓存机制可能掩盖问题但实现真实栈组件时这绝对是个隐性 bug。用equals是最稳的。复杂度方面操作时间复杂度说明pushO(1)两次入栈操作常数时间popO(1)两次出栈操作常数时间topO(1)直接取主栈栈顶getMinO(1)直接取辅助栈栈顶空间O(n)最坏情况严格递减序列辅助栈与主栈同规模压缩写法的好处是在平均情况随机数据下辅助栈的规模通常远小于主栈但在最坏情况数据严格递减下它和主栈一样大空间复杂度依然是 O(n)。这个“最坏情况”在面试时一定要主动分析因为它直接引出后面的进阶优化思路。3. 同步与比较细节真正决定代码一次过的地方3.1 为什么“小于等于”而不是“小于”很多初学者写辅助栈时压入条件用的是val minStack.peek()而不是val minStack.peek()。这个差异在弹出时会埋下大坑。举个例子压入[1, 1]。如果压入条件用辅助栈只会存入第一个1。接着弹出第二个1主栈弹出元素值等于辅助栈栈顶都是1辅助栈被同步弹出此时minStack空了getMin()直接异常。原因就是有两个相等的元素都是最小值但辅助栈里只给它们留了一个位置弹掉一个之后另一个还在栈里却没有对应的最小值记录了。用就不会有这个问题。第一个1压入辅助栈第二个1也压入辅助栈弹出时一一对应永远不丢状态。3.2 不同实现方案的边界对照辅助栈方案看起来简单实际写起来还是有很多“看着没错但一跑就错”的地方。我把几个最容易踩的坑整理了一下易错点错误示范正确做法原因空栈 getMin直接peek()不判空先判空再 peek或按题目约定操作空栈无最小值可言比较相等值用比较两个 Integer用equals()或intValue()超过 127 的 Integer 没有缓存保证压入条件保证重复最小值不丢状态辅助栈初始化主栈和辅助栈独立判断isEmpty主栈压第一个元素时必压辅助栈保证后续的peek()永远有值pop 同步条件每次 pop 都弹辅助栈仅当主栈弹出值等于辅助栈栈顶时才弹否则会丢失历史最小值这五个坑前四个我在教学时见人踩过无数次第五个则是“没理解辅助栈含义”的表现——辅助栈里存的不是“当前所有元素的衍生物”而是“最小值历史的精简记录”。只有在最小值真的被弹出主栈时辅助栈才需要回退。3.3 实测一个边界用例为了让你对边界情况有更直观的感觉我们走一遍完整用例push(-2) → 主栈[-2] minStack[-2] getMin() -2 push(0) → 主栈[-2,0] minStack[-2] getMin() -2 push(-3) → 主栈[-2,0,-3] minStack[-2,-3] getMin() -3 pop() → 主栈弹出-3 minStack弹出-3 getMin() -2 top() → 0这段走完你会发现关键转折点就在pop()弹出-3的那一刻——如果辅助栈没有在push(-3)时压入-3那么pop()时辅助栈停在-2上getMin()的值就是对的但如果你压的是-1也同步弹辅助栈变成了空整个结构就崩了。所以“辅助栈只记录关键节点”这个设计真的需要在弹栈的瞬间做一次精确的“回退判断”。4. 进阶优化单栈差值法把辅助栈整个干掉4.1 差值法数学原理辅助栈方案虽然简单可靠但空间复杂度是 O(n)而且最坏情况下辅助栈和主栈一样大相当于翻倍的内存。能不能只用一个栈就搞定可以这就是经典的差值法。它的核心思想是栈里不再存原始值而是存每个元素与“压入时最小值”的差值。通过一个变量维护当前最小值利用差值正负来反向推导历史状态。具体来说维护一个全局变量min代表当前栈内最小值。push(val)如果栈空直接压入valmin val。否则压入diff val - min。如果diff 0说明val比当前最小值还小更新min val。pop()弹出栈顶diff。如果diff 0说明弹出的是当前最小值最小值要回退到上一个状态即min min - diff。如果diff 0最小值不变。top()栈顶diff如果是负数说明栈顶元素就是当前最小值返回min。否则返回min diff。getMin()直接返回min。为什么要存差值而不是存原始值因为原始值本身没有携带“历史信息”而差值天然携带了“这个元素跟当时最小值差多少”的信息。diff 0就表示“我破了纪录”并把旧纪录封存在min - diff这个表达式里——弹出的瞬间能算出来。来看一个例子push(3) → 栈顶3 min3 push(5) → diff2 min3 // 存的是5-32 push(2) → diff-1 min2 // 2-3-1更新最小值 top() → diff-1 min2 pop() → diff-1 min 2 - (-1) 3 // 恢复到上一个最小值3注意push(2)的时候我们压进去的是-1这个负数不但告诉我们“新元素比当前最小值小 1”还在弹出时帮忙恢复了旧最小值 3。一箭双雕。4.2 差值法的完整代码与边界检验用 Java 写一版class MinStack { private DequeLong stack; private long min; public MinStack() { stack new ArrayDeque(); } public void push(int val) { if (stack.isEmpty()) { stack.push(0L); min val; } else { long diff (long) val - min; stack.push(diff); if (diff 0) { min val; } } } public void pop() { long diff stack.pop(); if (diff 0) { min min - diff; } } public int top() { long diff stack.peek(); if (diff 0) { return (int) min; } return (int) (min diff); } public int getMin() { return (int) min; } }这里我特意用了long因为val - min可能溢出。比如min是Integer.MIN_VALUEval是Integer.MAX_VALUE差值是 42 亿多超出int范围。转换成long是安全做法。如果直接存int差值这个用例会算出错误的数值进而污染min的恢复逻辑。边界检验场景push 差值pop 行为top 行为结果是否正确空栈压入首元素压入0minval弹出0min不变返回min正确新元素比min大diff0min不变返回mindiff正确新元素比min小diff0min恢复为min-diff返回min正确连续多个更大元素diff 都是正值逐层弹出min一直不变每层计算恢复原值正确压栈里存 0 而不是存val是因为首元素就是最小值差值必然是 0这样 top 返回min 0也是正确的逻辑统一。4.3 两种方案对比什么时候用哪个对比维度辅助栈方案差值方案代码可读性高逻辑直观低需要理解数学原理空间占用最坏 O(2n)O(n)只用一个栈溢出风险无直接存原值有必须用 long面试沟通成本低三两句话讲清高但能体现深度适用场景工程代码、团队协作内存敏感、技术展示我的建议是刚开始刷题用辅助栈面试时候两种都讲。先把辅助栈写对再主动提一句“如果考虑优化空间可以用差值法把辅助栈省掉”然后迅速画出核心逻辑。面试官通常都会对这个延伸印象深刻。5. 这样一类题的通用解题框架从最小栈到单调栈5.1 最小栈背后的数据结构思维最小栈看似只有一个“设计题”的壳但它背后其实藏着一个更通用的思想当一个数据结构只支持“从一端进出”时你如何维护它内部的某种统计信息统计信息可以是最小值最小栈、最大值最大栈、甚至是“栈内元素的累加和”、“栈内每个元素的排名”。通用套路无非三种平行结构开第二个同类结构同步记录统计信息。辅助栈就是这种。节点自包含每个节点里带上“从栈底到当前位置的统计量”。比如每个节点存{value, currentMin}。差值编码把统计量的相对变化直接编进存储值里用额外变量维护绝对基准值。差值法就是这种。这三种思路不止用于栈。你把它套到队列上就是“单调队列求滑窗最大/最小值”套到线段树上就是“区间最小/最大值查询”的雏形。最小栈其实是在帮你建立一种直觉任何需要“历史最优”的数据结构都可以在设计时考虑“如何分层存储统计状态”。5.2 相关题目的迁移套路顺着这个框架你再去看下面这些题会发现解法几乎可以平移过去带最大值操作的栈把辅助栈的判断条件反过来只在更大值出现时压入。队列的最大值需要一个单调递减的双端队列每次入队时从队尾弹出比当前元素小的值队首永远是最大值——这其实就是把辅助栈从“栈”推广到了“双端队列”。单调栈求下一个更大元素栈里存下标或值始终保持栈内元素单调递减或递增。出栈的瞬间就是“找到了答案”的时刻。数据流中的中位数两个堆做中位数本质上也是用“平行结构”维护统计状态——一个大顶堆存左半一个小顶堆存右半。最小栈是所有这些题里最朴素的入门题因为它只涉及最基础的“最小值”统计且栈的进出规则简单。但一旦你掌握了“辅助数据结构和主数据结构同进退”这个设计模式遇到任何“自定义数据结构 O(1) 查询”的题都能快速找到切入方向。5.3 面试时如何层层递进答题说点实用的。我在模拟面试里见过太多人拿到这道题就闷头写辅助栈写完收工。这样其实浪费了一道好题。合理的展示节奏应该是这样的第一层先说出朴素思路有什么缺陷——遍历求最小值不满足 O(1)维护单一变量无法应对弹栈。这能展示你有分析能力。第二层提出辅助栈方案写代码分析时间和空间复杂度。这部分占主要篇幅。第三层主动提优化。可以说“辅助栈最坏情况空间是 O(n)如果面试者愿意我还可以用一个栈加差值把空间省掉”。然后简要解释差值法的数学原理。第四层如果面试官追问进一步说清楚“为什么差值法能用 long 避免溢出”“如果题目增加一个 getMax 怎么办”——后者其实就是再维护一个对称的辅助栈聊起来很自然。这几层讲完基本可以覆盖这道题的所有考察点。我在实际辅导中按这个节奏走完的候选人几乎没有在这道题上失过手。5.4 从刷题到工程辅助栈的真实应用场景最后说一点可能出乎意料的事MinStack并不只是刷题层面的玩具。真实工程里撤销系统、编辑器操作栈、浏览器前进后退都会有类似需求。举一个常见的例子编辑器实现了多级撤销Undo每一步操作都可能改变当前文档的某些统计状态比如“当前选中区域的最小值”“当前文本长度”。当用户连续撤销时历史状态必须跟着回退——如果你只存了一个“当前值”撤销到一半就彻底丢了上下文。解决的思路和最小栈一模一样用一个平行栈记录每次操作前的状态快照。差别只在于工程里快照可能很大所以会做增量存储、软引用甚至序列化压缩但数据结构层面的骨架就是辅助栈那个“同步同进退”的套路。这道题刷不刷得出来是面试的事但这个设计模式能不能内化是真会影响你后续写框架代码的边界的。我当年刚工作时在一个简易配置中心里实现“配置覆盖链”最初只维护了一个全局最小值变量每次回滚配置段就出 bug。后来意识到这就是一个典型的最小栈场景把单值变量换成辅助栈结构问题立刻消失。从那以后我就特别看重这类基础题的“工程迁移能力”。所以别把它只当成一道 LeetCode 157 号标签下的题目来背。理解它的核心思想——用一个与主结构同步的辅助结构保存“也需要回退的统计状态”——你会拥有一个能迁移到好多场景的底层思维模型。