做力扣hot100有一阵子了第155题“最小栈”可以说是我印象最深的一道简单题。说它简单因为代码量确实不大核心解法几行就能写完说它印象深是因为这题几乎每次刷都有新体会而且面试里出现频率极高它考察的不是“会不会用栈”而是“在特定约束下怎么重新设计一个数据结构”。今天就把这题的两个主流解法、完整推导过程、我踩过的坑、以及面试官可能会追问的东西一次讲清楚。如果你正在刷hot100或者准备面试想快速过一遍高频题这篇可以直接参考。很多人看到题目第一反应是维护一个变量记住最小值不就完了真这么简单它就不会出现在hot100里了。最小栈真正的难点在于你不仅要能快速拿到当前栈的最小值还要在pop之后让最小值“自动回退”到上一个状态。这就意味着单一变量是不够的你需要设计一套机制把最小值的变化历史存下来。这题的两个经典解法本质上是两种不同的“历史记录”策略一种用额外栈存历史一种把历史编码进栈元素本身。下面我按思考的递进顺序把这两个方案完整拆开讲一遍。1. 题目到底在考什么核心需求与思路拆解1.1 最小栈题面速读与真实考点先看题目要求设计一个支持push、pop、top、getMin四个操作并且能在常数时间O(1)内返回最小值的栈。这题在力扣上的难度标的是“中等”但它经常和各种简单栈题放在一起讨论原因就是它考察的不是某个API的用法而是“数据结构设计”的思维。push、pop、top这三个操作用系统自带的栈就能做到O(1)关键是getMin怎么在O(1)内返回当前栈中的最小值。最常见的暴力做法是调用getMin时遍历一遍整个栈找出最小值再返回时间复杂度是O(n)。题目明确要求O(1)这就在告诉你必须用空间换时间在数据进入栈的同时把最小值的变化信息记录下来。这里有个很容易被忽略的细节栈的特点是“后进先出”所以你不仅要维护“当前最小值”还要能在弹出元素后恢复到“弹出之前的最小值”。这个“可回退”的需求是这题区别于普通“找最值”问题的关键也是设计辅助结构时的核心约束。1.2 为什么不能只用一个变量记住最小值假设我们用一个min变量每次 push 时更新它。比如依次 push 3、5、2、1min分别为 3、3、2、1看起来很顺利。但接下来连续执行两次 pop 操作第一次 pop弹出的是 1也就是当前最小值此时栈里还剩 3、5、2正确的最小值应该变成 2可问题是min变量已经被赋值为 1弹出 1 之后它并不知道上一个最小值是 2而且也没有任何途径能找回这个信息。这就是单一变量方案的核心缺陷它只记录了“当前结果”没有记录“结果的历史变化轨迹”。一旦最小值对应的元素被弹出历史信息就断了。用一个简单比喻这就好比登山的时候只记最高海拔但下山时不记得曾经到过哪个垭口自然无法回退到上一个高峰的海拔。所以要解决这个问题思路就很清晰了必须把最小值的历史变化过程保存下来。最简单的做法就是再开一个栈专门记录“到目前为止的最小值”这就是下面要讲的辅助栈方案。1.3 O(1)复杂度的本质数据结构和算法的配合做题的时候最容易忽略的是“为什么辅助栈能保证 O(1)”。很多人只是记住了代码却说不清原理。这里的关键在于辅助栈的栈顶永远维护着“主栈当前状态下的最小值”。也就是说辅助栈的高度和主栈保持一致或者保持一致的状态映射主栈 push 一个元素进栈时辅助栈同步记录“当前全局最小值”主栈 pop 时辅助栈也跟着 pop。这样任何时刻getMin都只需要读取辅助栈的栈顶元素而栈顶操作本身就是O(1)整个过程完全不依赖栈里有多少个元素。从工程角度看这就是典型的“缓存思想”——用一个额外的数据结构把需要频繁查询的结果提前维护好查询时直接命中。日常开发里这种思路也特别常见比如缓存热点数据、维护前缀和数组等本质都是空间换时间。把最小栈这个题想透了再遇到类似设计题思路会开阔很多。2. 解法一辅助栈双栈法设计与完整实现2.1 同步栈与不同步栈两种辅助栈设计变体辅助栈法的核心设计有两种变体我建议你先掌握第一种因为它逻辑最简单面试时最不容易出错。第一种是“同步压栈”主栈 push 一个元素时无论它是否比当前最小值小辅助栈都压入“当前全局最小值”。比如当前最小值为 2现在 push 一个 5辅助栈照样 push 2。这样主栈和辅助栈高度完全相同pop 时两边同时 pop根本不需要额外的判断条件代码非常清爽。第二种是“只在更小/相等时压栈”当新元素比辅助栈栈顶当前最小值小或相等时才向辅助栈压入否则辅助栈不动。这样可以节省一些空间因为重复的、较大的元素不会占用辅助栈。但代价是pop 时需要判断当前弹出的元素是否等于辅助栈栈顶如果相等才把辅助栈也弹出。这个判断在代码里看似简单实际上是最容易写错的地方尤其是用Integer对象比较时稍不注意就会踩坑。我个人的建议是面试或者刷题阶段直接用同步压栈方案。它很好解释逻辑也不容易出 bug。节省的那点空间在算法题里根本不重要面试官更在意的是你能不能写出稳定、正确的代码。2.2 同步压栈完整代码实现这里用三种主流语言各写一版方便你对照。先看 Java 版本我推荐用ArrayDeque而不是老的Stack类性能更好接口也更现代class MinStack { DequeInteger stack; DequeInteger minStack; public MinStack() { stack new ArrayDeque(); minStack new ArrayDeque(); } public void push(int val) { stack.push(val); if (minStack.isEmpty()) { minStack.push(val); } else { minStack.push(Math.min(val, minStack.peek())); } } public void pop() { stack.pop(); minStack.pop(); } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); } }C 版本更简洁一些直接用标准库的stackclass MinStack { private: stackint stk; stackint minStk; public: MinStack() {} void push(int val) { stk.push(val); if (minStk.empty() || val minStk.top()) { minStk.push(val); } else { minStk.push(minStk.top()); } } void pop() { stk.pop(); minStk.pop(); } int top() { return stk.top(); } int getMin() { return minStk.top(); } };Python 版本可以直接用 list 模拟栈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]注意 Java 版本中Math.min(val, minStack.peek())这种写法本质上就是同步压栈即使新元素更大辅助栈压入的依然是旧的最小值。这样辅助栈的每个位置都对应主栈在该位置时的全局最小值。2.3 复杂度分析与正确性验证时间复杂度方面四个操作都只涉及栈顶的 push、pop、peek复杂度都是O(1)。这一点很好理解。空间复杂度是O(n)辅助栈最多存储 n 个元素n 为已经 push 的元素个数。验证正确性最好的方式是手动跑一遍状态变化。我们依次执行以下操作看两个栈的变化操作主栈内容辅助栈内容getMin 结果push(5)[5][5]5push(3)[5, 3][5, 3]3push(4)[5, 3, 4][5, 3, 3]3pop()[5, 3][5, 3]3push(1)[5, 3, 1][5, 3, 1]1从表里能清楚看到辅助栈的栈顶就是主栈当前的最小值。弹出 4 之后辅助栈也随之弹出 3getMin依然能正确返回 3。这就是“同步记录历史”的威力即使弹出的是最小值辅助栈栈顶也恰好是上一个状态的最小值完全不需要额外恢复操作。3. 解法二差值法常数空间优化的思路与实现3.1 差值法的核心数学原理辅助栈方案简单、稳定但它需要一个额外的栈空间复杂度是O(n)。如果面试官追问“能不能少用一份空间”你就得拿出第二个方案用差值法把空间利用压到极致。差值法的思路是主栈里不直接存原始元素而是存“当前元素与当前最小值的差值”。同时用一个变量min记录当前的最小值。具体规则如下栈为空时第一个元素直接入栈这里存一个0同时令min x栈非空时对于新元素x计算差diff x - min并将diff入栈如果diff 0说明x比当前最小值还小则更新min xgetMin直接返回min。初看可能觉得绕但核心逻辑在于栈里存的是“差值”而不是元素本身。为什么这样可以呢因为x和min之间存在线性关系知道其中一个和差值就能反推另一个如果栈顶差值diff 0说明入栈时元素不小于当时的最小值那么当前栈顶“实际元素”就是min diff如果栈顶差值diff 0说明入栈时这个元素本身就是新的最小值那么当前栈顶“实际元素”就等于min。弹出的时候更巧妙。看栈顶差值diff如果diff 0说明当前弹出的元素大于等于最小值那么弹出它不会影响min直接弹就好了如果diff 0说明当前弹出的元素正是最小值所在弹出后最小值要“回退”到上一个最小值。而旧最小值和当前元素的关系是diff x_new - old_min因此old_min x_new - diff。又因为弹出时x_new就是当前的min所以new_min min - diff。你看整个过程中我们只用了栈本身和一个变量就实现了所有操作。这就是差值法的核心数学基础。3.2 必须注意的边界与溢出问题差值法虽然省了空间但边界细节比辅助栈多得多这里要重点强调几个坑第一个坑是溢出。我们用diff x - minJava 的int范围是-2^31到2^31-1。如果x是2147483647min是-2147483648两者的差已经超过int的表示范围。所以实际写代码时要把diff用long来存否则会算错。这是我亲手踩过的坑在力扣上就是“Wrong Answer”非常隐蔽。第二个坑是栈为空时调用getMin或top这是非法的力扣不会测这种情况但面试时最好主动和面试官确认一下题目的约束条件。第三个坑是弹出后恢复最小值时min - diff这个操作也可能会超出int范围所以min本身也建议用long来存最后返回时再转回int。3.3 差值法完整代码与运行过程模拟下面是 Java 实现注意long的使用class MinStack { DequeLong stack; long min; public MinStack() { stack new ArrayDeque(); } public void push(int val) { long x val; if (stack.isEmpty()) { stack.push(0L); min x; } else { stack.push(x - min); if (x min) { min x; } } } 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 diff); } else { return (int)min; } } public int getMin() { return (int)min; } }C 实现也是同样的思路用long long避免溢出class MinStack { private: stacklong long stk; long long minVal; public: MinStack() {} void push(int val) { long long x val; if (stk.empty()) { stk.push(0); minVal x; } else { stk.push(x - minVal); if (x minVal) minVal x; } } void pop() { 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 diff); return (int)minVal; } int getMin() { return (int)minVal; } };我们手动模拟一遍这个流程。依次执行以下操作操作栈内差值min 变量说明push(5)[0]5第一个元素存 0min5push(3)[0, -2]3diff 3-5 -2 0更新 min3push(4)[0, -2, 1]3diff 4-3 1 0min 不变getMin[0, -2, 1]3直接返回 3pop[0, -2]3diff1 0min 不变push(-1)[0, -2, -4]-1diff -1-3 -4 0更新 min-1top[0, -2, -4]-1diff-4 0返回 min即 -1pop[0, -2]3diff-4 0new_min -1 - (-4) 3恢复从这个表格可以看出差值法确实只用一个栈加一个变量就完成了所有操作空间复杂度降到了O(1)。但也能看出它的问题整个逻辑对“差值符号”的依赖很强而且可读性明显不如辅助栈。面试时如果面试官不追问我个人更建议用辅助栈作为首选答案差值法作为一个补充亮点展示即可。3.4 两种解法的选型对比这里直接给一张对比表方便你记忆对比维度辅助栈双栈法差值法常数空间空间复杂度O(n)O(1)代码可读性高逻辑直观低需要理解差值含义出错概率低高尤其容易溢出面试推荐度首选作为进阶方案展示适用语言通用需要注意 long 类型支持如果这是在线笔试我建议直接写辅助栈保命要紧。如果是现场面试我会先写辅助栈然后主动提一句“如果限制空间可以改用差值法”再在面试官追问时详细展开。这样既展示了扎实的基础又体现了思维深度。4. 力扣刷题与面试实战常见问题与排查技巧4.1 高频 Bug 清单与排查思路这题代码量不大但我在实际刷题和看别人代码时发现几个高频 Bug这里全部列出来你可以对照自查。第一个 Bug 是不同步辅助栈时pop 判断写错。很多人会写成if (stack.peek() minStack.peek())这在 Java 里用Integer类型比较时大于 127 的值会返回 false导致辅助栈弹出逻辑失效。正确的做法是用equals方法或者干脆用同步压栈方案从根源上回避这个问题。第二个 Bug 是辅助栈判空顺序写反。比如在push时写成if (val minStack.peek())但如果minStack是空的就会抛异常。记住永远先判空再访问栈顶。第三个 Bug 是差值法里忘了把diff转成long。如果题目测试数据里有极端大数比如2147483647和-2147483648int溢出算出的差值完全错误整个栈就废了。这个 Bug 非常隐蔽因为大多数测试用例都是普通数字只有上万个极端数据才能测出来。第四个 Bug 是 pop 之后没有更新min。辅助栈方案如果同步弹出就不会有这个错但如果你采用了“只在更小/相等时压栈”的变体又忘了在弹出最小值时把辅助栈也弹出那么getMin会一直返回已经不在栈里的值。4.2 从最小栈延伸出去hot100 栈题串联思路最小栈虽然在力扣上标的是中等难度但它是 hot100 里非常基础的一道栈设计题。刷这题时我强烈建议你顺便把几个相关的栈题一起过一遍形成知识网络效果比孤立刷题好得多。有效的括号考察栈的最基本用法——匹配与消除是栈入门第一题。每日温度单调栈的典型应用维护一个递减栈来找到右侧第一个更大的元素。接雨水经典难题用单调栈计算面积和最小栈中“维护最小值状态”的思路有异曲同工之妙。最小栈偏向“数据结构设计”要求多个操作协调、状态可回退。你会发现最小栈的核心思想是“用辅助结构维护状态”这和单调栈维护“单调性状态”、括号匹配维护“期望状态”本质上一脉相承。能把这几道题串起来理解你对栈的理解会上升一个层次。4.3 面试官可能会追问的问题怎么答这题在面试里被追问的频率很高我整理了几个常见的 follow-up以及一个比较稳的回答思路。第一个追问如果不用额外空间怎么实现O(1)的getMin这就是前面说的差值法。你把差值法的原理讲清楚说明为什么用long存储差值可以避免溢出基本上就能让面试官满意。第二个追问如果支持并发访问怎么办这是一个开放题。你可以说在push、pop、getMin上加锁或者用ConcurrentLinkedDeque加原子变量维护min。这类问题考察的是工程意识不要求标准答案关键是展示你对线程安全的理解。第三个追问既然辅助栈能轻松实现为什么不直接封装一个类这个问题有点“陷阱”意味。你可以回答正是因为它本质上是一个可供复用的“数据结构”所以这题才叫“最小栈”——它考察的就是你设计一个类的能力体现在构造函数、方法签名、状态一致性这些细节上。你可以顺便提一下你的实现中MinStack类本身不依赖额外全局变量所有状态都封装在实例内部这也是面向对象设计中“高内聚”的体现。5. 实操心得与刷题建议这题已经刷过很多遍了每次带人刷题时我都会强调一个动作拿张纸把栈的状态变化一步步画出来。不管是辅助栈里的两个栈还是差值法里的那个差值栈 min变量你只要能把每一步的数据变化画清楚代码几乎是水到渠成的事根本不用背。另外一个小技巧是如果你发现自己写出来的代码在力扣上“Wrong Answer”不要急着看题解而是构造一个包含大量 push、pop、getMin 交替操作的小数据手动跑一遍往往很快就能定位问题。这种“手动模拟栈状态”的能力刷题阶段非常重要笔试时的调试速度全靠它撑着。还有一个经验是力扣 hot100 里的题不需要按顺序刷按主题刷效率更高。把最小栈和括号匹配、单调栈相关题目放在同一天做你会明显感觉到知识点之间的迁移效率很高。反过来如果你只是零散地刷题今天一道栈明天一道二叉树大脑很难形成系统性的记忆。最后想说这题给我最大的收获是“状态可回退”这四个字。以前写代码总觉得记录一个变量就万事大吉最小栈让我意识到任何需要“回退”的场景都需要一个记录历史的载体。这个思想在算法题里无处不在比如函数调用栈、编辑器的撤销重做、浏览器的前进后退本质上都是“线性历史回退”。想通了这一点你刷的就不只是一道题而是一类问题的共性规律。