这道题我刷了三遍，每次都有新体会。LeetCode Hot 100里的第155题“最小栈”，表面上是道简单偏中的栈设计题，但它在面试里出现的频率高得离谱，而且问法往往会从“实现一个能取最小值的栈”升级成“你的解法空间复杂度能不能再压一压”“如果允许O(1)取最大值呢”。这篇就把最小栈从题目本质、辅助栈解法、空间优化差值法，到面试回答的细节坑位，一次说透。

1. 题目拆解：核心需求与考察意图

1.1 原题到底在问什么

155.最小栈的核心要求非常精简：设计一个支持 push、pop、top 操作，并且能在常数时间内检索到最小元素的栈。常规栈的三个操作 push、pop、top 本身都好说，关键是最后这个getMin() 必须在 O(1) 时间内返回当前栈内的最小值。

很多人第一次看到题目会本能地想：那我用一个变量 minVal 记录最小值不就行了？push 的时候更新一下，getMin 直接返回 minVal。这个思路能过一半测试，但在 pop 操作上会露馅：如果被弹出的元素恰好就是当前记录的最小值，那新的最小值是多少？你需要知道上一个状态的最小值，而一个普通变量根本没有“历史记录”的能力。这就是这道题真正的考察点——栈是有状态的，最小值也有状态，状态和状态之间必须能正确回退。

1.2 为什么它能进 Hot 100

这道题能进 Hot 100，不是因为算法有多炫技，而是因为它把“用空间换时间”、“状态同步”、“边界条件处理”三个基本功揉在了一个看似简单的框架里。面试官用它能快速判断一个候选人：

• 是否真的理解栈的先进后出特性，而不是背过 API 就完事；
• 有没有意识到”维护全局极值“和”维护历史极值序列“的区别；
• 能不能在 O(1) getMin 的约束下主动引入辅助数据结构；
• 更进一步，能不能想到用差值编码把辅助栈的空间省掉。

我看到不少人在牛客和小红书上抱怨“Hot 100 动态规划题刷吐了”，但说实话，最小栈这道题的思维方式和很多动态规划里“状态压缩”的思路是相通的：你不一定需要记住所有完整状态，只要把能推导出下一步状态的关键差异保留下来就够了。后面聊差值法的时候你会更直观地感受到这一点。

2. 辅助栈解法：最主流也是最稳的方案

2.1 思路演进：从“记录最小值”到“同步最小值栈”

回到 1.1 里那个minVal变量的问题。它失效的根源是，最小值被弹出后，无法知道之前的最小值是多少。那自然的想法就是：把每次 push 之后当前栈内的最小值也存下来。

这正好可以用一个辅助栈来实现。辅助栈的栈顶永远保存当前数据栈的最小值，数据栈每 push 一个元素，辅助栈就 push 一次“当前最小值”；数据栈每 pop 一个元素，辅助栈也跟着 pop。这样两个栈的高度永远一致，getMin 时直接读辅助栈栈顶即可。因为每次操作都是常数次栈顶读写，所以 push、pop、top、getMin 全部是 O(1)。

你可能要问：辅助栈里存那么多重复的最小值，是不是浪费？比如依次 push 5、1、1、1，辅助栈就是 [5, 1, 1, 1]，确实有冗余。但这里的冗余是有意义的——它让“状态回退”变得极其简单：数据栈弹出最上面的 1 时，辅助栈也弹出 1，剩下的辅助栈顶还是 1，说明当前数据栈的最小值依然是 1。如果辅助栈不存重复值，只在值更小的时候入栈，那么当你弹出最小值的重复副本时，辅助栈根本不知道该不该跟着弹，很容易出错。所以保底方案宁可多存，不可存错。

2.2 代码实现：以 Python 为例

用 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 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.stack.pop() self.min_stack.pop() def top(self) -> int: return self.stack[-1] def getMin(self) -> int: return self.min_stack[-1]

这里有一个细节：我在 push 里用的是val <= self.min_stack[-1]，也就是等于最小值时也入辅助栈。这是为了保证重复最小值在 pop 时能正确同步。假设辅助栈只在严格小于时入栈，那么 push 两个 1，辅助栈只有一个 1；接下来数据栈 pop 掉一个 1，辅助栈跟着 pop，就变成空栈了，但数据栈里还剩一个 1，最小值应该还是 1。这就不对了。

2.3 能不能省掉辅助栈里的重复值

有一种常见优化：辅助栈只在“严格小于当前最小值”时入栈，pop 时只有当弹出的元素等于辅助栈栈顶时才弹出辅助栈。这样确实能省空间，代码逻辑也能保证正确：

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.pop() == self.min_stack[-1]: self.min_stack.pop() def top(self) -> int: return self.stack[-1] def getMin(self) -> int: return self.min_stack[-1]

注意这里 push 时用的是<=，pop 时用==判断。等等，这里需要想清楚：push 时等于也入栈，那 pop 时如果等于，弹出的元素和辅助栈顶相同，辅助栈弹出后，如果下面还有相同的值，最小值依然正确；如果下面没有相同的值，说明数据栈里也没有这个最小值了。这逻辑是对的，而且空间确实更省。我在实际刷题中使用这种写法更多，因为它在正确性和空间效率上做到了不错的平衡。

不过面试时我通常先讲最朴素的“同步栈”版本，等面试官追问优化时再给出“条件入栈”版本。这样节奏更好，也更能展示思考的层次。

3. 差值法：把空间复杂度压到 O(1)

3.1 核心思想：不存“前一刻的最小值”，而是存“差值”

辅助栈能正确工作，本质上是因为它记录了每个时刻的最小值历史。可不可以连这个历史都不完整记录，只用常数个变量就完成任务？LeetCode 讨论区里最经典的做法是差值法。

差值法的思路是这样的：在数据栈里存的不再是元素本身的值，而是当前值与“当前最小值”的差。同时用一个变量minVal记录当前的最小值。每当 push 一个新值val时：

• 如果val >= minVal，直接存入差值val - minVal，最小值不变；
• 如果val < minVal，说明最小值要更新，存入差值val - minVal（此时差值为负），然后把minVal更新为val。

pop 时，从栈顶取出差值diff：

• 如果diff < 0，说明当前栈顶元素就是最小值，而且 pop 会让最小值回退到“上一个最小值”；
• 恢复上一个最小值的办法：prev_min = minVal - diff。

我一开始看这个恢复公式是完全懵的，后来自己推了一遍才明白。假设 push 过程中，某一次遇到了新最小值new_min，它小于当时的旧最小值old_min。在那一时刻，入栈的差值是new_min - old_min，是负的，同时minVal变成了new_min。现在要 pop 这个元素，我们知道diff = new_min - old_min，而当前的minVal = new_min，所以old_min = minVal - diff。本质就是解一元一次方程。

top 操作需要根据栈顶差值还原真实值：

• 如果diff >= 0，真实值就是minVal + diff；
• 如果diff < 0，真实值就是当前的minVal，因为栈顶元素就是最小值本身，至于minVal会被更新是 pop 时才做的事。

getMin 直接返回minVal，依旧是 O(1)。

3.2 代码实现与取数边界陷阱

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: return self.min_val else: return self.min_val + diff def getMin(self) -> int: return self.min_val

这里有几个非常关键的坑：

1. 第一个元素入栈时，栈里没有“当前最小值”可减。我把它特殊处理成压入 0，再把min_val设为val。这个初始化必须单独判断，否则 diff 会减出一个 undefined 状态。
2. 差值可能超出 int 范围。如果最小值和当前值一个极大一个极小，val - self.min_val可能溢出。比如 min_val 是 -2^31，val 是 2^31 - 1，差值已经超出 32 位 int 的表示范围。Java/C++ 里用 long 就能解决，Python 的 int 是任意精度的所以没事，但如果你写 C++ 版本，int真的会溢出，这点面试时主动说出来是加分项。
3. pop 时恢复 min_val 的符号方向。self.min_val = self.min_val - diff，因为 diff 为负，所以等于加上一个正数，正好回到旧最小值。我见过有人写成min_val += diff，那就不对了，恢复后就比当前更小了。
4. top 时返回真实值。很多人会把差值法的 stack 直接当成普通栈用，top 返回stack[-1]，这是错的。栈里存的是差，不是真实元素值。

差值法并不是银弹。它虽然把辅助栈省了，但代码可读性明显变差，而且引入了整数溢出问题，还要区分 diff 的正负。实际工程里我几乎不会用这种写法，但在算法面试的语境下，它体现了你对数据结构“状态压缩”的理解，是能把普通答案提升一档的亮点。

4. 工程视角：从 LeetCode 到真实业务场景

4.1 最小栈在哪些地方真的有价值

每次聊算法题，总有人问“这玩意除了面试还能干嘛”。最小栈这个模式其实在真实场景里是有原型的。我举几个例子：

• 文本编辑器的撤销功能。编辑器需要维护操作历史，同时还要知道历史上某个状态下的最小/最大字号、最短/最长段落长度等统计信息。如果你只记录当前值，撤销一次后就丢了上下文；如果你记录完整快照，内存又扛不住。辅助栈的“分层快照”思路恰好是一种折中。
• 浏览器或移动端的导航路径。用户访问路径本质上是个栈，回退时你需要恢复到上一个状态。如果还要实时统计路径里的最值（比如最长的停留页面），就是最小栈的路子。
• 系统监控中的滑动窗口极值。这个更接近单调队列而不是最小栈，但如果你限制窗口只能从一端弹出，最小栈的辅助栈思路可以直接套用过去。

我觉得最有启发的一点是：当你需要维护某种“全局统计量”，而操作又会改变这个统计量的历史状态时，辅助结构或差值编码几乎是通用解法。理解了这个，你看到的就不只是 155 题，而是一类状态同步问题。

4.2 多语言实现差异与踩坑清单

我平时主要用 Python 刷题，但也在 Java 和 C++ 里各写过一遍这题。不同语言的坑差异挺大：

Java 用ArrayDeque模拟栈是最推荐的，push和pop都是 O(1)，而且没有Stack类继承 Vector 带的历史包袱。C++ 里用std::stack最简单，但如果想控制底层容器，也可以声明为std::stack<int, std::vector<int>>，这样top()返回的引用在 push 扩容后可能失效，这个点很冷门，但问出来很能体现水平。

另外在 Java 里用差值法时，我建议把所有栈元素和min_val都声明成long，这样 push 时计算val - min_val就不会溢出，代价是内存占用翻倍。结合 LeetCode 的数据范围，long完全够用，属于“用空间换安全”的典型取舍。

4.3 扩展思考：最大栈和双端极值问题

面试官在 155 题的基础上常见连环问是“如果我要 getMax 怎么办”。答案其实很简单：再建一个辅助栈，同步维护最大值。最小栈和最大栈各用各的辅助栈，互不干扰。再进阶一步，问“如果我要求 O(1) 同时取最小值和最大值”，还是一个套路，两个辅助栈还是比值法，只是代码更长。

还有一种问法我之前遇到的是“设计一个队列，支持 O(1) 取最小值”。这个就是单调队列的经典应用了，和最小栈刚好互补：栈用辅助栈，队列用单调队列。刷完 155，我建议顺手把 239 滑动窗口最大值也刷了，这样“栈场景的最值维护”和“队列场景的最值维护”就都覆盖了，面试时被问到的胜率会大很多。

5. 刷题经验与热度辨析：为什么 Hot 100 总有它

5.1 我三刷这道题的真实感受

第一次刷 155 是在我刚接触 LeetCode 的时候，看题解直接用辅助栈，代码一敲就过了，但说实话没完全理解，过两天就忘了。第二次刷是准备校招，那时候我会自己先写一遍再对题解，开始注意<=和<的细节，也写了一遍差值法，终于想明白恢复公式。第三次刷是复习高频题，我开始想一道题能不能几种解法都写一遍，辅助栈写完之后又用差值法写了一遍，并且把两种写法都发了题解笔记。

三刷下来最深的体会是：高频题的真正价值不在“会做”，而在“能讲”。面试官不会只满足于你写对，他要听你解释为什么这么设计，pop 时间辅助栈会不会造成错误，你考虑过哪些边界。所以刷题阶段就要逼自己做“输出式学习”：写完别着急下一题，先闭眼给自己讲一遍思路。

5.2 和“hot100 动态规划”热搜的关系

有人看到热门搜索里有“hot100 动态规划”和“hot100题”这样的词，可能奇怪最小栈和动态规划有什么关系。确实，155 题本身不是一个动态规划问题，它没有状态转移方程、没有最优子结构。但差值法的“只保存差异而不是完整状态”思路，和动态规划里常见的状态压缩（比如背包问题滚动数组压缩掉一维）是同构的——都是利用历史状态中的不变/规律部分，来减少存储规模。

所以我的建议是：不要孤立地刷题。把 Hot 100 里的栈题、队列题、单调栈题当成一个“状态维护问题集”来刷，尤其关注它们之间的异同。当你在最小栈里理解了“状态快照与状态恢复”，再去刷 739 每日温度（单调栈）、239 滑动窗口最大值（单调队列）、以及一些区间动态规划问题时，会觉得底层思维是通的。

5.3 常见错误与面试引导建议

我把身边同学和评论区高频出现的问题整理成表，方便自查：

面试时我习惯这样引导：先讲清楚“为什么一个普通变量不够”，再说辅助栈怎么解决状态回退问题，然后追问空间时自然引出差值法。如果面试官面无表情，可以主动用一个小例子演示 pop 后 getMin 的变化过程，比如依次 push 2、4、1、3，然后 pop 掉 1，getMin 应该回到 2，最后 pop 掉 4，getMin 应该保持 2。手动模拟一遍比干说十句都管用。

整体来说，最小栈这道题是一个“门槛不高，上限很高”的题目。背答案很容易，能把朴素版本、优化版本、溢出风险、扩展问法全串起来，才算真正吃透了。