刷 LeetCode 的人迟早会撞上这题它在热题 100 里的位置非常靠前也是面试现场出现频率极高的一道看似简单、实则全是细节的经典题。题目要求设计一个栈在支持常规 push、pop、top 的基础上额外提供一个 getMin 方法让调用方能在常数时间内获取当前栈内的最小值。很多人第一反应是我遍历一遍不就行了但一旦操作量上来这种思路就直接废了。今天我把这道题的几种主流解法、背后的设计逻辑、以及几次实战里栽过的坑全部捋一遍尤其是差值法和链表节点法这两个容易被忽略的进阶思路希望能帮你彻底吃透它。无论你是刚刷完链表、准备进入栈队列专题的新手还是已经在面试冲刺阶段想查漏补缺的老手这篇文章都值得你花上半个小时细读。我会从最直观的辅助栈方案讲起逐步过渡到空间更省的数学方案最后补充链表建模的思路全程给到可直接抄走的代码和边界处理细节。1. 题目拆解别被最小栈三个字骗了1.1 这道题到底在考什么先看清楚题目在问什么。它要求我们自己设计一个栈结构对外暴露四个操作push、pop、top、getMin并且要求全部在 O(1) 时间复杂度内完成。前三个操作是栈的标配没有悬念。关键就在最后一个 getMin 上——你要随时知道栈里面最小的那个值是多少而且不能去遍历。这题被归为栈类但它本质上考的是两个东西第一你对空间换时间这个基本策略的理解第二你对如何在动态变化的数据集合中用最小的额外代价维护一个聚合信息的建模能力。栈的 push 和 pop 只会影响栈顶元素但栈里的最小值可能在任何一次 pop 之后发生变化比如你把当前最小值弹走了那新的最小值是谁如果不在某个地方记录下来你就只能重新遍历一次栈。有些题解会把它称为双栈问题或者辅助栈问题但其实单靠一个主栈也能做只是需要在节点上或者差值上做文章。这题的面试价值非常高因为它可以从一个非常简单的需求出发延伸出至少三种风格完全不同的实现方案每一种都能考察不同的能力点。1.2 暴力解法为什么活不过三秒先看看大多数人第一时间的想法主栈正常存数据getMin 的时候遍历整个栈找出最小值。这么做在功能上完全正确代码也极其简单但时间复杂度是 O(n)。如果你的操作序列是先连续插入 n 个元素再连续调用 n 次 getMin那总时间复杂度就是 O(n²)。在刷题平台的大数据量下这种写法几乎必然超时。我见过不少人在这里有个误区觉得LeetCode 的测试数据没那么严格说不定能混过去。不要有这种侥幸心理这题作为热题 100 里的关卡测试用例对复杂度的卡控是相当认真的。而且退一步讲就算你暴力能过面试官追一句你能别 O(n) 吗场面一样会很尴尬。所以从一开始就要往 O(1) 的方向走。1.3 一个关键问题不用额外空间真的行吗顺着暴力解法的痛点往下想想要 getMin 是 O(1)就必须在接受 push 的时候就把某些信息存下来。这个信息是什么最简单直观的答案就是当前的最小值。你可以在每次 push 的时候顺便记录一下到目前为止的最小值是谁然后 getMin 直接返回这个记录。这里有个很微妙的点一旦你选择把每个时间点的最小值都保存一份其实就已经是在用空间换时间了。想要完全零额外空间要么把最小值的信息编码到已有数据里比如差值法要么把它塞进节点结构里比如链表节点法。后面我会把这几条路都展开讲你可以对比一下它们的空间开销和实现复杂度感受一下不同取舍的滋味。2. 解法一双栈法——最经典也最容易写错的实现2.1 用记账本的思路理解辅助栈双栈法是最容易理解的做法主栈正常存元素辅助栈专门记到目前为止出现过的历史最小值。你可以把辅助栈想象成一个记账本每一次 push 时都在本子上记下此时栈里的最小金额不管新来的钱是大是小都如实抄一遍。这样一来辅助栈的栈顶永远是当前的最小值getMin 只需要看一眼辅助栈的栈顶。这种做法的核心原因只有一个当主栈进行 pop 时栈顶元素被弹走全局最小值可能变也可能不变。如果最小值被弹走了你就必须知道上一个最小值是多少——辅助栈正好能提供这个信息因为它记录的是完整的历史。这就是空间换时间的本质我多存一份历史换来的是所有操作都能在 O(1) 内完成。2.2 两套变体每次都记 vs 只在更小的时候记双栈法有两个变体。第一个变体是每一次 push 都往辅助栈压入当前最小值这样主栈和辅助栈的高度始终一致pop 的时候两个栈一起弹逻辑最简单。第二个变体是只有在新元素小于等于当前最小值的时候才往辅助栈里压这样辅助栈的高度小于等于主栈省一点空间但 pop 的时候需要判断一下当前弹出的元素是不是等于辅助栈栈顶是的话才弹辅助栈。两个变体的正确性都没问题差异只在常数空间上。我个人的建议是面试讲第一版因为它不容易错、好讲清楚练习时把第二版也写一遍因为这样能帮你加深对辅助栈栈顶代表什么的理解。下面给第二版的参考代码class MinStack { private: stackint stk; stackint minStk; public: void push(int x) { stk.push(x); if (minStk.empty() || x minStk.top()) { minStk.push(x); } } void pop() { if (stk.empty()) return; if (stk.top() minStk.top()) { minStk.pop(); } stk.pop(); } int top() { return stk.top(); } int getMin() { return minStk.top(); } };2.3 现场最容易踩的坑相等值要不要压入这里有一个很多第一次写的人都会栽的细节在第二版变体里判断条件写成x minStk.top()行不行答案是——不行。你想想如果栈里现在的最小值是 2此时又 push 了一个 2这个 2 虽然不比最小值小但它同样是最小值。如果只在小于的时候才压入辅助栈那么当要 pop 掉栈里最后一个值为 2 的元素时由于它相等辅助栈的栈顶也是 2一样会被误弹导致辅助栈提前把最小值弹没了后续 getMin 就会出错。所以判断条件必须写成x minStk.top()。另一种口味是每次 push 都压入当前最小值那样就完全没有这个问题代价是辅助栈空间多存一倍的重复值。两者各有取舍但在面试现场我建议你先把每次同步记录写出来然后再提一句其实还可以优化成只在更小或相等时压入省一点空间这样会显得你既有正确解法又有优化意识。3. 解法二差值法——用数学换空间3.1 差值法的核心原理辅助栈固然好用但面试官经常会追问一句你还能不能用更少的空间这时候差值法就登场了。差值法的思路非常巧妙主栈里不保存原始值而是保存当前元素与当前最小值的差值。这个差值可以是正数、负数或零它的正负号本身就携带着这个元素是不是当时的最小值这一关键信息。先约定一个全局变量 minVal 表示当前栈内真正的最小值。push(x) 的时候如果栈为空直接设 minVal x压入差值 0如果不为空计算 diff x - minVal。如果 diff 0说明 x 比当前最小值还小那就更新 minVal x。然后把 diff 压栈。pop 的时候如果栈顶的 diff 是负数说明当前栈顶元素正是当时被更新为最小值的那一个pop 之后最小值要恢复成上一个最小值。这里有个数学关系假设 push 时的旧最小值是 oldMin新最小值 x 比 oldMin 小那么 diff x - oldMin也就是 diff 是一个负数。当我们弹出这个元素后新的最小值应该是 oldMin它等于 x - diff 新minVal - diff。如果栈顶的 diff 是非负数说明这个元素没有影响过最小值minVal 就不用动。这个方案最优雅的地方在于它把历史最小值的信息编码进了差值的符号里。数学上是完全自洽的。3.2 边界条件为什么必须上 long long差值法有个特别阴险的陷阱整数溢出。举个例子如果当前最小值是 INT_MIN也就是 -2147483648此时 push 进来一个 INT_MAX2147483647计算 diff 2147483647 - (-2147483648) 4294967295这个数已经远远超过了 int 的表示范围直接溢出成负数整套逻辑瞬间崩盘。解决办法很简单在所有涉及差值计算的地方先把 int 转成 long long 再运算。这样一来就算极端情况也能保证差值不会溢出long long 最大到 9 位数以上足够容纳 int 的两个极端差值。如果你用的是 Python 就更不用担心了Python 的整数是任意精度的不会溢出。这里贴一份 C 的完整实现class MinStack { private: stacklong long stk; long long minVal; public: MinStack() { minVal 0; } void push(int x) { if (stk.empty()) { minVal x; stk.push(0LL); } else { long long diff (long long)x - minVal; stk.push(diff); if (diff 0) { minVal x; } } } void pop() { if (stk.empty()) return; long long diff stk.top(); stk.pop(); if (diff 0) { minVal minVal - diff; } } int top() { long long diff stk.top(); if (diff 0) { return (int)minVal; } return (int)(minVal diff); } int getMin() { return (int)minVal; } };3.3 空间优化的真相与面试加分点差值法在空间上的优势是没有额外栈但它并没有把空间复杂度降到一个更低的量级——依然是 O(n)因为你自己维护的那个栈还是要存 n 个差值。不过它省掉了辅助栈那一整套存储空间常数因子更小而且它展示了你对数据建模的思考深度。面试的时候如果你能在辅助栈方案之后主动给出差值法是一个很明显的加分动作。但要注意差值法的代码比双栈法更容易写错特别是 pop 和 top 里对 diff 0 的分支判断以及 long long 的转换。我见过不少人在白板上写着写着就漏掉了 minVal minVal - diff 这一步结果整个栈的最小值越弹越错。建议你在练习时把测试用例设计得极端一点比如先压入 INT_MIN 再压入 INT_MAX再弹出来仔细验证每一行走的逻辑。4. 解法三链表节点法——面试里的加分答案4.1 把最小值塞进每个节点里除了双栈和差值还有第三种思路不额外开栈而是改造栈本身的存储结构。如果你用链表来实现这个栈那每一个节点可以不止存 val 和 next 指针还可以多存一个 min 字段表示从当前节点到栈底所有元素中的最小值。这其实是一种非常自然的设计——链表天然支持在头部插入和删除恰好契合栈顶操作。每次 push 的时候新建一个节点该节点的 min 取新元素的值和当前栈顶节点的 min中的较小值。getMin 只需要读取栈顶节点的 min 字段O(1) 搞定。pop 的时候把头节点移向下一个节点即可因为下一个节点里已经保存了它自己到栈底的最小值完全不需要额外计算。4.2 手写链表实现的完整代码如果你已经习惯了用语言自带的栈容器手写链表可能会让你感到陌生但恰恰是这种从底层构建数据结构的能力在面试中很受面试官看重。下面是一个简化的实现这里我直接用了一个哨兵头节点来简化边界相当于用空栈即只有一个 header 节点来表示struct Node { int val; int min; Node* next; Node(int v, int m, Node* n) : val(v), min(m), next(n) {} }; class MinStack { private: Node* head; public: MinStack() { head new Node(0, INT_MAX, nullptr); } void push(int x) { int curMin head-min; if (x curMin) curMin x; head-next new Node(x, curMin, head-next); } void pop() { if (head-next nullptr) return; Node* tmp head-next; head-next tmp-next; delete tmp; } int top() { return head-next-val; } int getMin() { return head-next-min; } };4.3 这种解法在考察什么链表节点法最直接的价值是它不需要依赖语言自带的 stack 容器而是完全靠你自己对节点和指针的理解来构建一个栈。面试官考察它往往是想看你对基础数据结构的掌握到底有多扎实以及你写代码时对空指针、内存释放这类边界细节的敏感程度。这个方案的空间复杂度也是 O(n)但它比辅助栈法更省空间而且访问局部性更好——因为最小值信息就在节点内部。这也能顺带引出关于栈的底层实现到底用数组还是链表的讨论。数组栈扩容有开销链表栈每个节点有额外指针开销两者各有适用场景。把这些细节聊透基本上这段面试就稳了。5. 常见问题与现场排查技巧实录5.1 栈空时的行为怎么定义题目通常给的接口是假定每次调用 pop、top、getMin 时栈都是非空的但实际工程里你不可能这么乐观面试官也喜欢问你边界条件。C 的 stack::top() 在栈为空时是未定义行为实际跑起来可能返回一个垃圾值甚至崩溃。所以不管用哪种实现我都会建议在代码里加上判空保护比如 pop 时先检查非空、getMin 时如果栈空则返回一个特殊值或者直接抛出异常。工程上返回特殊值不如抛异常明确但在刷题场景里判空后返回 INT_MAX 也是一种常见的处理。5.2 面试高频连环追问这类题在面试里从来不只是一个写出来就结束的存在。常见追问包括如果 getMin 改成 getMax 怎么办其实思路完全一样把辅助栈的压入条件反向即可。如果允许操作是 O(log n) 呢那就可以用有序容器套平衡树每次维护当前最小值都是有序结构里最小的那个元素。如果再放宽到本质上就是要查询动态集合的极值那就会延伸到堆、单调栈、线段树那一大串内容去了。我建议你在准备这道题的时候把辅助栈“差值”节点字段这三种方案都写在同一个笔记里它们其实是同一道题从三个不同角度切入的延伸。下面整理了一张速查表方便你冲刺复习时快速回忆实现方案额外空间代码复杂度易错点双栈每次同步O(n) 辅助栈低几乎无双栈仅更小压入O(n) 最坏情况少于前一种中相等值判断条件差值法O(n) 常数更小高diff 的符号分支链表节点法O(n)中高空指针与内存释放5.3 刷题提速与自我验证的技巧最后聊一个非常实际的操作建议这道题写完以后一定要用一组让最小值多次变动的用例去自测。比如依次执行 push(3)、push(5)、getMin()、push(2)、getMin()、pop()、getMin()、push(1)、getMin()。如果你用的是双栈变体二这一步就能立刻暴露出相等值是否压栈的问题如果用差值法它能让 pop 后 minVal 的恢复逻辑得到验证。我个人的习惯是先用 python 跑一遍枚举测试把每一步操作后的栈状态和最小值都打出来再回到 C 代码逐行对照这样能把逻辑上的疏漏很快找出来。另外如果面试时时间紧张我建议你把双栈法作为首选答案三到五分钟内写完并讲清楚再用剩余时间补差值法的思路。不要一上来就写差值法万一写错了反而是减分项。先求稳再求亮眼这个顺序最安全。我个人在实际操作中的体会是这题真正难的从来不是想出辅助栈而是把辅助栈为什么这样做讲明白。如果你能把pop 之后的最小值怎么恢复这个问题回答得流畅自然那说明你是真的理解了栈的运作机制而不是背了个题解。最后建议你把三种方法分别在纸上各写一遍重点练差值法因为它是所有解法里最能检验你边界处理功底的一个。