刷LeetCode的人绕不开hot100这套题单而155题最小栈在里面的地位很特别它看起来简单却是面试现场出镜率最高的栈类题之一。我第一次见它也没当回事以为就是栈上多维护一个最小值变量结果前两次提交都被边界数据教做人了。后来把这道题彻底吃透才发现它真正想考的不是“能不能实现”而是“在O(1)时间拿到最小值”这个硬约束下你能否想到用历史状态来兜底。这篇文章是我对hot100最小栈的一次完整复盘适合正在刷hot100题准备面试的读者也适合想搞懂辅助栈、差值存储这类底层套路的同学。1. 题目到底在考什么三个隐藏考点1.1 原题要求与常规直觉LeetCode 155的题目要求很短设计一个栈支持push、pop、top、getMin四个操作push和pop沿用标准栈行为top返回栈顶元素getMin返回当前栈内最小的元素所有操作都要求O(1)时间复杂度。题面越短往往意味着坑越深。最核心的难点就在“所有操作O(1)”这句话上。栈的push、pop、top天然就是O(1)栈的数组实现或链表实现都能轻松做到。但getMin如果每次通过遍历栈内元素来找最小值复杂度就成了O(n)。所以这道题的全部矛盾点集中在怎么用O(1)的时间拿到当前栈里的最小值并且在pop之后还能继续正确回答这个问题。很多人的第一反应是维护一个min成员变量在push时顺手比较更新。这个思路对了一半push操作确实可以O(1)更新最小值。但pop的时候问题就暴露了。假设当前栈里依次压入3、5、2min变量记录到2如果把栈顶的2弹出栈里还剩3和5此时真正的最小值是3可min变量还停留在2无法自动回退。因为min变量只记住了“当前最新最小值”却没有记住每一个历史阶段的最小值。这正是最小栈区别于普通栈的核心难点栈的内容是动态变化的你必须在任何一次pop之后依然能正确回答这个动态集合的最小值。1.2 三个隐藏考点把这层纸捅破之后这道题其实在考察三件事历史状态记录能力。栈会弹元素最小值信息不能只存当前一个值还要能在弹栈后恢复旧值。这是最关键的认知转变。同步结构设计。最自然的解法是设计两个栈数据栈加辅助栈同步压弹。这个设计思路可以迁移到很多场景比如括号匹配、表达式求值。边界条件的严谨度。重复最小值、连续pop最小值、以及初始空栈调用getMin都会让不严谨的实现当场露馅。也正因为这三点最小栈在面试里的梯度设计得很好新手能写个大概老手能在细节上展现功力。我后来发现很多公司面试官喜欢拿它开场不是因为它难而是因为它能快速检验一个人的代码洁癖和边界意识。2. 方法一双栈解法最稳的核心方案2.1 双栈的工作原理双栈解法的核心思想很直白在普通数据栈之外再加一个辅助栈minStack。数据栈负责所有常规操作minStack则专门记录“数据栈当前状态对应的最小值”两栈保持同步。具体的规则是这样的push(val)数据栈压入val辅助栈同时压入Math.min(val, minStack栈顶)这样辅助栈的栈顶始终是“包括刚压入元素在内的当前栈内最小值”。pop()数据栈弹出栈顶辅助栈同步弹出栈顶。弹出之后辅助栈的新栈顶恰好就是数据栈剩余元素的最小值。top()返回数据栈栈顶。getMin()返回辅助栈栈顶。这里最容易被忽略的细节是push时辅助栈的比较应该用还是?答案是。我举个例子连续压入三个2如果比较用第二个2在辅助栈中无法压入因为2 2不成立辅助栈里从头到尾只有一个2。此时先弹出两个2数据栈里还剩一个2但辅助栈已经被弹空了getMin直接报错或者返回错误结果。用才能保证每一个重复最小值在辅助栈里都有对应的记录pop时一对一弹出任何时刻辅助栈栈顶都能正确指向当前最小值。这个细节我当年第一次写的时候也错过了是测试数据里连续重复值把我教育了一顿。后来我把这个教训沉淀成一条自查规则凡是涉及同步栈的题先想想重复元素会不会导致状态丢失。2.2 双栈的代码实现Java实现class MinStack { private DequeInteger stack; private DequeInteger minStack; public MinStack() { stack new ArrayDeque(); minStack new ArrayDeque(); minStack.push(Integer.MAX_VALUE); } public void push(int val) { stack.push(val); 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(); } }Python实现class MinStack: def __init__(self): self.stack [] self.min_stack [float(inf)] def push(self, val: int) - None: self.stack.append(val) 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的minStack初始化时压入Integer.MAX_VALUEPython的min_stack初始化为[float(inf)]。这个哨兵有两个作用一是让minStack在第一次push时不会peek到空栈二是如果空栈状态下误调用了getMin返回的是一个极大值而不是抛异常。虽然LeetCode的测试用例不会在空栈时调用getMin但加了哨兵之后代码更健壮面试讲起来也更严谨。这里还有个小知识点为什么用Deque而不用Java早期的Stack类。Stack继承自Vector内部所有方法都有synchronized同步开销而且API风格比较陈旧Deque的push、pop、peek方法语义更贴近栈是现在的主流写法。两者在LeetCode上都能通过但写Deque会让面试官觉得你的Java基础是跟进过现代实践的。时间复杂度上四个操作全部是O(1)。空间复杂度是O(n)准确说是需要2n规模的辅助存储。这是典型的空间换时间也是这道题最正统的题解。3. 方法二差值存储法一个常被误解的优化3.1 差值法的原理双栈解法虽然稳妥但面试官经常会追问一句“能不能少用一个栈”这时候就可以引出差值存储法。先说结论这个方法并不能把空间复杂度降到O(1)它本质上仍然是O(n)的空间只是从两个栈变成一个栈常熟因子更小。很多网上的文章把它写成O(1)空间那是错的。栈里每个元素都要存一个diff值怎么可能O(1)但“少用一个辅助栈”这个优化方向在面试讨论里是合理且有价值的。差值法的核心思路是数据栈里不存原始值而是存“当前值与当前最小值的差值”同时用全局变量min记录当前栈内的最小值。因为差值里编码了这个元素是否比当时的最小值更小的信息所以可以在pop时把最小值的历史恢复出来。这个思路有点像记账你不需要记每一笔工资的绝对数额只要记下每一笔相对上一笔的变化就能在期末推出任意时刻的账目。3.2 推导过程约定push(val)时栈中压入的diff val - min这里的min是压入前的最小值。如果diff 0说明val大于等于当前最小值那这个val不会改变minmin保持原样。如果diff 0说明val比当前最小值还小那么新的最小值就是val本身所以更新min val。pop时弹出一个diff如果diff 0说明这个位置对应的元素不是最小值当前min不变。如果diff 0说明这个位置对应的元素就是当前的最小值。此时要恢复它压入之前的最小值。因为当时diff 当前min - 旧min稍微移项就能得到旧min 当前min - diff。注意diff是负的所以恢复出来的旧min会比当前min大逻辑上完全正确。top时取出diff如果diff 0真实值 diff min。如果diff 0真实值就是min因为压入的时候它成了新的最小值。这里最关键的坑是溢出。int的最小值是-2147483648最大值是2147483647两者之差最大能到4294967295直接超出int范围。比如先push一个2147483647再push一个-2147483648如果所有字段都声明为intdiff在计算时就已经溢出后面的getMin和top都会拿到错误结果。所以Java实现里diff和min必须用long。这是我自己实际测试时踩过的坑一开始想偷懒用int结果用例一复杂就错。3.3 差值法完整代码class MinStack { private DequeLong stack; private long min; public MinStack() { stack new ArrayDeque(); } public void push(int val) { long x val; if (stack.isEmpty()) { stack.push(0L); min x; } else { long diff x - min; stack.push(diff); if (diff 0) { 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; } return (int) (diff min); } public int getMin() { return (int) min; } }这段代码逻辑上完全成立但可读性和可维护性都明显不如双栈。我个人的建议是面试先讲双栈拿稳基本盘如果面试官明确追问能否优化空间再拿出差值法同时主动指出空间复杂度仍然是O(n)只是少用一个栈。这种“主动纠正常见误解”的表达反而比背一个所谓的最优解更让面试官认可。4. 面试现场从暴力思路一步步推到最优解4.1 引导式答题节奏面试题很少只考察写对更看重的是你“怎么想到的”。准备最小栈的时候可以把答题过程组织成清晰的四步先说最直观的暴力解法getMin遍历整个栈时间复杂度O(n)。这个答案明显不满足题目要求面试官自然会追问优化。提出维护单个min变量push时更新。这里主动说出它的缺陷——pop掉最小值后无法回退因为没有保存任何历史信息。这一步非常关键说明你不是在背答案而是真正理解瓶颈在哪。提出双栈方案既然单个min不够用就用一个辅助栈保存每个历史时刻的最小值。数据栈和辅助栈同步压弹getMin直接返回辅助栈栈顶。到这里我们已经拿到了完整满足O(1)约束的最优解。如果面试官继续追问空间优化再补充差值存储法把推导过程和溢出风险讲清楚并强调它也只是常数优化不是渐进意义上的空间优化。这样讲下来全程没有“背答案”的痕迹而且每一步都是在上一步暴露的问题上做修补面试官很容易顺着你的逻辑走。4.2 边界条件与测试用例代码写完主动说出你会用哪些测试用例来验证是很加分的动作。我整理了一张最小栈的必测用例表场景操作序列预期结果常规操作push 3, push 5, push 2getMin返回2弹出最小值接上例pop一次getMin返回3重复最小值push 2, push 2, pop一次getMin依旧返回2先大后小push 5, push 1getMin返回1先小后大push 1, push 5getMin返回1连续弹出到空push 1, push 2, pop, pop栈空再push 9后getMin返回9第三行正是逼出这个细节的场景。我建议把“连续压入相同最小值再逐个弹出”当作最小栈的检查用例写完代码先在脑子里跑一遍能挡住一半以上的低级错误。5. 常见问题与排查实录5.1 现象pop之后getMin返回错误最典型的场景先压入3、5、2pop掉2之后getMin应该返回3实际却返回2有时直接抛异常。原因分析只要辅助栈没有在pop时同步弹出或者push时没有把较小值压入辅助栈就会出现数据栈和辅助栈不同步的情况。排查办法很简单在每个操作之后打印两个栈的内容逐步对照。这类问题基本都是同步逻辑写岔了。5.2 现象第一次push时抛EmptyStackException原因分析辅助栈没有初始化边界哨兵push时执行Math.min(val, minStack.peek())对一个空栈调用了peek。解决方法是初始化的时候压入Integer.MAX_VALUE。这行代码看起来不起眼但每逢新写的栈类题我都会提醒身边人先加上它真的每次都在救人。5.3 现象差值法在提交时结果错乱原因分析int溢出。之前我已经踩过这个坑所以现在一律建议把diff和min全部声明为long返回时再强转回int。因为真实值范围在int内强转不会丢精度。特别注意不要在push时先算int类型的差再赋值给long那样迟早溢出要先把val转成long再做减法。5.4 现象LeetCode提示无法编译这类问题大多是方法签名不符。LeetCode的MinStack要求pop()返回void而很多本地工具类写习惯了的人会顺手把pop设置成返回int。提交前先扫一眼题目给的方法签名这个小动作能省下两分钟的调试时间。另外Java里用ArrayDeque时注意它不能存放null元素不过这道题的数据流不会出现null一般不用操心。还有一个容易被忽视的点LeetCode的类名固定为MinStack构造函数需要无参。如果是调试本地测试类类名可以随便取但提交时一定要用回MinStack别被平台判编译错误。6. 从最小栈看hot100题单里的栈类套路6.1 最小栈和单调栈不是一回事很多人在刷hot100题单的时候会把最小栈和单调栈混在一起记。两者的共同点是都用栈维护某种“历史极值”或“有序状态”但结构完全不同。最小栈是辅助栈思想数据栈和辅助栈同步压弹辅助栈保存每个时刻的全局最小值。单调栈则是栈内元素保持严格单调递增或递减的栈经典应用场景是找“下一个更大元素”比如hot100里的每日温度、柱状图中最大的矩形。单调栈在入栈时会先把破坏单调性的元素弹出去弹出的过程往往就是计算答案的过程核心是利用局部单调性压缩无效比较。对比来看维度最小栈单调栈核心思想用辅助栈记录历史最小值用单调性消除无效比较压栈规则双栈同步压入当前最小值破坏单调性时先弹出旧元素典型场景任意时刻查询栈内最小值下一个更大/更小元素、最大矩形面积复杂度四个操作单次O(1)每个元素至多出入栈一次均摊O(n)理解这个区别比单纯背题有用得多。很多人以为hot100题就是动态规划刷到底其实像最小栈、字符串解码、每日温度这些都属于栈这一类题型各不相同但底层能力都是“用栈去维护一种动态状态”。6.2 刷题建议按题型归纳而不是按题号刷我的习惯是拿到hot100题单之后先不看题号顺序而是按分类走数组与哈希、双指针、栈、二叉树、动态规划、图论。最小栈作为栈分类的第一题非常适合建立“辅助结构”的直觉。一旦理解它后续很多题目都能触类旁通比如有效的括号、简化路径、逆波兰表达式求值本质上都是在用栈还原某种上下文关系。题目本身不难但它是很好的基础模块。把这个模块吃透了再去碰单调栈题目就不会发怵。刷题数量重要但把最小栈这种“简单题”当中等重要的事来对待把边界条件和为什么讲清楚比无脑刷三道题收获更大。7. 写在最后一点个人体会我第一次写最小栈的时候栽在这个细节上第一次看差值法的时候觉得思路好巧妙但真正自己动手写还是选了双栈。原因很实在双栈代码短、逻辑直、不容易出错适合工程和面试环境差值法更像是在展示数学思维适合作为优化方案的补充展示。如果你正在准备面试我的建议是先用双栈拿稳基本盘再把差值法的推导过程练习一遍确保自己能在白板上解释清楚diff小于0时oldMin min - diff的来龙去脉。刷hot100题到一定量之后你会发现最小栈这道题考察的根本不是语法而是你是否具备“在动态状态下维护历史答案”的意识而这种意识恰好就是栈类题目的通用底层能力。最后分享一个小技巧写完任何栈类题目都别急着提交。依次跑一遍“重复元素连续压入再连续弹出”“先压最小值再压更大值”“先压大值再压小值”这三组用例比盲目提交试错省时间得多。这个习惯我保持到现在基本上栈类题目第一遍提交就能过。