这道题我刷了三遍每次都有新体会。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这里有几个非常关键的坑第一个元素入栈时栈里没有“当前最小值”可减。我把它特殊处理成压入 0再把min_val设为val。这个初始化必须单独判断否则 diff 会减出一个 undefined 状态。差值可能超出 int 范围。如果最小值和当前值一个极大一个极小val - self.min_val可能溢出。比如 min_val 是 -2^31val 是 2^31 - 1差值已经超出 32 位 int 的表示范围。Java/C 里用 long 就能解决Python 的 int 是任意精度的所以没事但如果你写 C 版本int真的会溢出这点面试时主动说出来是加分项。pop 时恢复 min_val 的符号方向。self.min_val self.min_val - diff因为 diff 为负所以等于加上一个正数正好回到旧最小值。我见过有人写成min_val diff那就不对了恢复后就比当前更小了。top 时返回真实值。很多人会把差值法的 stack 直接当成普通栈用top 返回stack[-1]这是错的。栈里存的是差不是真实元素值。差值法并不是银弹。它虽然把辅助栈省了但代码可读性明显变差而且引入了整数溢出问题还要区分 diff 的正负。实际工程里我几乎不会用这种写法但在算法面试的语境下它体现了你对数据结构“状态压缩”的理解是能把普通答案提升一档的亮点。4. 工程视角从 LeetCode 到真实业务场景4.1 最小栈在哪些地方真的有价值每次聊算法题总有人问“这玩意除了面试还能干嘛”。最小栈这个模式其实在真实场景里是有原型的。我举几个例子文本编辑器的撤销功能。编辑器需要维护操作历史同时还要知道历史上某个状态下的最小/最大字号、最短/最长段落长度等统计信息。如果你只记录当前值撤销一次后就丢了上下文如果你记录完整快照内存又扛不住。辅助栈的“分层快照”思路恰好是一种折中。浏览器或移动端的导航路径。用户访问路径本质上是个栈回退时你需要恢复到上一个状态。如果还要实时统计路径里的最值比如最长的停留页面就是最小栈的路子。系统监控中的滑动窗口极值。这个更接近单调队列而不是最小栈但如果你限制窗口只能从一端弹出最小栈的辅助栈思路可以直接套用过去。我觉得最有启发的一点是当你需要维护某种“全局统计量”而操作又会改变这个统计量的历史状态时辅助结构或差值编码几乎是通用解法。理解了这个你看到的就不只是 155 题而是一类状态同步问题。4.2 多语言实现差异与踩坑清单我平时主要用 Python 刷题但也在 Java 和 C 里各写过一遍这题。不同语言的坑差异挺大语言栈实现主要坑点Pythonlist 负数索引第一个元素初始化容易漏slice 操作时间复杂度高不要用del stack[:-1]JavaDequeInteger用ArrayDequeArrayDeque 不允许 null用Stack类会有同步锁开销面试用 ArrayDeque 更专业Cstd::stack栈底不知道什么时候是 0差值法用 long 防溢出push和emplace别混Java 用ArrayDeque模拟栈是最推荐的push和pop都是 O(1)而且没有Stack类继承 Vector 带的历史包袱。C 里用std::stack最简单但如果想控制底层容器也可以声明为std::stackint, std::vectorint这样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 后最小值错误引入辅助栈或差值法辅助栈在时入栈重复最小值无法正确回退改为入栈pop 时无条件跟弹出栈顶辅助栈与数据栈不同步仅在相等时弹辅助栈top 返回值没转换差值和真实值混淆根据 diff 正负恢复真实值差值法忽略溢出C 等强类型语言会出错用 long初始化时拿空栈计算 diff运行时错误特判第一个元素面试时我习惯这样引导先讲清楚“为什么一个普通变量不够”再说辅助栈怎么解决状态回退问题然后追问空间时自然引出差值法。如果面试官面无表情可以主动用一个小例子演示 pop 后 getMin 的变化过程比如依次 push 2、4、1、3然后 pop 掉 1getMin 应该回到 2最后 pop 掉 4getMin 应该保持 2。手动模拟一遍比干说十句都管用。整体来说最小栈这道题是一个“门槛不高上限很高”的题目。背答案很容易能把朴素版本、优化版本、溢出风险、扩展问法全串起来才算真正吃透了。