刷Hot 100刷到155题的时候很多人会有一种错觉最小栈嘛不就是给栈加一个min变量吗我第一次就是带着这种自信点开题目的然后被getMin()必须O(1)这个要求正正地拍在墙上。155题的设计很阴险——它不考你会不会用栈考的是你能不能想明白栈顶被弹掉之后次小值从哪里来这个问题。当时我翻热门题解区发现评论区一半人在问辅助栈的原理一半人在纠结重复元素我就知道这题没有看上去那么简单。这篇文章把最小栈的完整思路拆开讲从暴力解法为什么必挂到辅助栈的两种实现再到O(1)空间的差值法最后把面试官常问的追问链一并列出来。适合正在刷Hot 100的选手也适合马上要面试、想把这类设计题讲透的人。看完你不仅能AC还能在被追问为什么的时候答得滴水不漏。1. 题目到底在考什么为什么暴力解法必挂1.1 155题在Hot 100里的真实定位Hot 100里的题目大多是重算法的比如二叉树、动态规划、图论155最小栈算是其中的一股清流它更像一道微型系统设计题。题目要求实现一个类四个方法全部O(1)时间复杂度push(int val)入栈pop()弹出栈顶top()获取栈顶元素getMin()获取栈内最小值前缀155指的是它在题库里的编号在Hot 100栈系列里属于开篇题。这道题在面试里的出现频率高到什么程度我自己面过的十来场算法面试中原题出现过两次变体出现过一次。它不挑岗位后端、客户端、甚至基础架构方向的面试都可能抽到因为考察的东西非常底层你懂不懂状态记录这件事。1.2 单变量暴力思路的致命弱点很多人的第一反应跟我一样在栈类里加一个int minVal每次push的时候顺手更新它getMin直接返回不就行了我立刻发现自己忽略了pop。举一个最简单的例子push 2 - min 2 push 3 - min 2 push 1 - min 1 pop() - 弹掉1此时栈里是 [2, 3]但 min 变量还停在1 getMin() - 返回1直接错了问题在于当栈顶被弹出的恰好是当前最小值时你需要立刻知道剩下那些元素里的最小值是什么。单靠一个min变量根本回答不了这个问题因为你没有记录过上一个最小值是什么。你当然可以退一步getMin时临时遍历一遍栈或者对栈内元素排序但那就不是O(1)了。所以这道题真正要你解决的矛盾是在pop发生之后如何让最小值这个信息也跟着正确回退。只要把这个矛盾想明白了辅助栈的解法几乎是水到渠成的。1.3 对O(1)这个条件的正确理解O(1)的含义不是快而是操作耗时与栈内元素数量无关。这意味着你不能在任何方法里用循环、递归或排序去现算答案。设计这类题有一个非常实用的思考角度如果你需要实现一个历史状态的回溯——即最小值随弹栈而还原——就必须在数据变化发生时把过去的信息预先记录下来。这个记录过去的动作本质就是空间换时间。记住这个角度后面所有解法你都串得起来。2. 辅助栈解法以空间换时间的正统思路2.1 核心思想用另一个栈记住每个时刻的最小值辅助栈的解法思路可以一句话说明主栈负责正常出入辅助栈负责记录历史上每一个时刻的栈内最小值。打个比方就像你记账时用两本账本主账本记录每笔流水辅助账本记录到今天为止账户里最少剩过多少钱。只要每一笔账进来时同步更新辅助账本那么无论之后怎么取钱你瞄一眼辅助账本的最新一行就能知道当前状态下的最低值。在最小栈里两个栈的最新一行永远对齐主栈弹出一个元素时辅助栈也在同一时刻弹出对应记录于是辅助栈的栈顶永远等于主栈当前状态下的最小值。这个性质由push和pop两个操作共同维护。2.2 同步辅助栈最好写的版本同步版本的特点是主栈和辅助栈元素个数完全一致辅助栈第i个位置存的是主栈第i个元素入栈那一时刻的最小值。C实现class MinStack { private: stackint st; stackint minStack; public: MinStack() {} void push(int val) { st.push(val); if (minStack.empty()) { minStack.push(val); } else { minStack.push(min(val, minStack.top())); } } void pop() { st.pop(); minStack.pop(); } int top() { return st.top(); } int getMin() { return minStack.top(); } };Python实现class MinStack: def __init__(self): self.st [] self.min_st [] def push(self, val: int) - None: self.st.append(val) if not self.min_st: self.min_st.append(val) else: self.min_st.append(min(val, self.min_st[-1])) def pop(self) - None: self.st.pop() self.min_st.pop() def top(self) - int: return self.st[-1] def getMin(self) - int: return self.min_st[-1]随着操作序列走一遍push 3: st [3], minSt [3] push 5: st [3, 5], minSt [3, 3] push 2: st [3, 5, 2], minSt [3, 3, 2] pop: st [3, 5], minSt [3, 3] getMin: 3同步版最大的优点是逻辑零分支push方法里甚至连要不要更新最小值都不用判断min()函数天然处理了所有情况。pop时也不用判断一起弹就完事。2.3 不同步辅助栈省空间但要小心重复值不同步版本只在最小值真正被刷新的时候才入辅助栈。也就是说只有当val minStack.top()时才把val push进辅助栈。pop时只有当st.top() minStack.top()时才把辅助栈也弹一个。C实现class MinStack { private: stackint st; stackint minStack; public: MinStack() {} void push(int val) { st.push(val); if (minStack.empty() || val minStack.top()) { minStack.push(val); } } void pop() { if (st.top() minStack.top()) { minStack.pop(); } st.pop(); } int top() { return st.top(); } int getMin() { return minStack.top(); } };这个版本在单调递增的输入下空间效率极好比如不断push 1, 2, 3, 4, 5辅助栈始终只有1个元素。但这里藏着一个非常典型的坑条件必须是不能是。我实际刷题时就踩过这个坑。假设我错误地写成了val minStack.top()然后执行push 5 push 3 - 3 5辅助栈入3 push 3 - 3 3 为 false辅助栈不入 pop() - 弹出3且 st.top() minStack.top() 3辅助栈弹掉3 getMin() - 辅助栈顶变成5而主栈里明明还有一个3结果就是getMin返回5彻底崩掉。原因很简单两个相同的3第一个3入栈时记录了一次最小值3第二个3因为判断条件问题没有记录但pop时却没区分是哪一个3把记录给弹崩了。所以重复元素场景下要么入栈时用确保每个并列最小值都有记录要么pop时用更精确的计数方式。2.4 两个版本的对比与选型对比项同步版不同步版push逻辑无脑push当前min无分支仅当 val minTop 时pushpop逻辑两个栈一起pop无分支仅当弹出值等于辅助栈顶才pop最坏空间O(n)O(n)最好空间O(n)单调递增序列下O(1)代码量更少略多易错程度低重复值判断容易翻车我个人在实际刷题和面试手写时默认都用同步版代码短、正确性一眼可见、边界条件少。不同步版更适合作为面试中的空间优化方案口头提出来展示你考虑过空间效率但不建议在紧张的面试环境下手写它。3. 再进一步O(1)空间的差值解法真的可行吗3.1 差值法的数学逻辑辅助栈的空间复杂度最坏是O(n)面试官自然会追问能不能做到O(1)空间答案是能但解法很奇技淫巧。做法是栈里不存原始值存每个元素与入栈时栈内最小值的差值diff再用一个变量min记录当前全局最小值。定义入栈值为x入栈前的栈内最小值为minBefore则diff x - minBefore如果 diff 0说明 x minBefore最小值不需要更新以后要恢复元素值用min diff即可如果 diff 0说明 x 比之前的最小值还小入栈后最小值更新为 x以后恢复这个元素时它本身就是当前最小值直接返回minpop时只有一种情况需要恢复min弹出的栈顶diff 0说明这个被弹出的元素就是当前最小值本身那么入栈前的最小值应该是minBefore x - diff min - diffdiff是负数min - diff比min大正好回退到上一个最小值。3.2 完整实现与正确性验证C实现注意用long longclass MinStack { private: stacklong long st; long long minVal; public: MinStack() { minVal 0; } void push(int val) { if (st.empty()) { st.push(0LL); minVal val; } else { st.push((long long)val - minVal); if (val minVal) { minVal val; } } } void pop() { long long diff st.top(); st.pop(); if (diff 0) { minVal minVal - diff; } } int top() { if (st.top() 0) { return (int)minVal; } return (int)(minVal st.top()); } int getMin() { return (int)minVal; } };用一组数据走一遍正确性push 3: st空st[0]min3 push 5: diff5-32st[0,2]min3 push 2: diff2-3-1st[0,2,-1]min2 push 4: diff4-22st[0,2,-1,2]min2 top(): 栈顶diff20返回 224 pop(): 弹掉diff20min不变 pop(): 弹掉diff-10min 2-(-1)3恢复正确 top(): 栈顶diff20返回 325每一步的结果都对得上。这个解法在纯算法竞赛里算是一个漂亮的技巧但它有个致命前提diff的计算结果可能超出int范围比如min是INT_MIN、val是INT_MAX差值约为42亿多int装不下。所以必须用long long这也是为什么题目本身的int输入会让你额外警惕。3.3 为什么这种解法在工程中是下策先说结论差值法我只推荐在两类场景使用——一是面试中被明确追问能不能O(1)空间时口头提思路二是纯粹为了好玩做算法练习。真正写生产代码我绝对不会这么干。原因有三可读性极差。return minVal st.top()这种表达写的人觉得妙看的人血压高。代码是写给同事读的辅助栈版本三行就能让任何人读懂差值法可能需要别人拿纸笔推导五分钟。溢出隐患。就算内部用long long一旦数据范围进一步扩大比如实际业务里出现64位整数这个方案又会面临新的溢出问题。工程上没人愿意为一个getMin制造一个潜在的雷。边界条件多。空栈时存diff0而不是常规语义pushes时首次入栈要特殊处理pop时还要根据diff符号决定是否回退min。每一步都容易写错测试起来也要额外覆盖很多序列。如果面试官真的想要空间O(1)的正规军通常还有另一个思路用链表实现栈每个节点同时存val和该节点入栈时的最小值这样只有一个栈结构空间还是O(n)但形式上没有第二个栈。这种答案面试中也很讨喜因为它展示了你在数据结构层面做文章的意识。struct Node { int val; int minVal; Node* next; Node(int v, int m, Node* n) : val(v), minVal(m), next(n) {} }; // push时 new Node(val, min(val, head-minVal), head) // getMin时直接返回 head-minVal本质上它还是同步辅助栈的思路只是把辅助信息塞进了每个节点内部。4. 面试实战追问链、易错点与变体延伸4.1 面试官最爱追问的四个问题把这题背下来不值钱能扛住追问才值钱。我根据实际面试经验整理了一条高频追问链追问1你辅助栈里存的到底是什么很多人答存最小值面试官会继续追问是哪一个最小值。正确回答是同步版存的是主栈每个元素入栈时刻的全局最小值不同步版存的是每次最小值发生更新时的那个最小值的快照。回答到这个粒度面试官才相信你真懂。追问2两个栈的pop必须同步吗这就引出了同步版和不同步版的区别。能主动说出同步版实现简单、不同步版空间可能更省但要注意重复元素这一问就算过了。追问3重复元素你怎么处理我建议的答法是先说结论入栈比较必须用然后立刻给出我上文那个反例连续push两个相同最小值后如果入栈用pop时会错误地把辅助栈里的最小记录弹掉。主动讲一个踩坑案例比背诵答案有说服力得多。追问4能不能空间O(1)把差值法的思路讲清楚同时强调需要long long防溢出、可读性差、工程上不推荐。大部分面试官到这里就会点头因为你的回答既展示了知识广度又体现了工程判断力。4.2 代码习惯与边界条件的隐藏坑除了逻辑本身代码习惯也会影响面试评价。有几个细节我每次写这道题都会注意一个是空栈问题。LeetCode的测试用例保证不会在空栈上调用top、pop、getMin但面试手写代码时最好主动确认这一点或者在方法开头加防御性判断。这个细节很容易被忽略但在现场面试里很加分。另一个是函数签名问题。LeetCode原题里pop不返回任何值top/getMin返回int。面试官很可能现场改题比如让pop返回被弹出的元素或者让getMin在空栈时返回一个指定值。动手写之前一定要确认清楚否则你按原题实现的类可能不符合对方的预期。还有一个小坑很多人把辅助栈叫minStack就完事了但没意识到同步版中辅助栈栈顶元素并不一定等于最后入栈的元素。比如push 5再push 3时辅助栈的栈顶是3但push 3之前辅助栈栈顶是5。理解这一点能帮你扛住你的辅助栈真的是栈吗这种问题——它就是一个普通栈元素是历史最小值序列。4.3 变体题最大栈、队列最小栈与组合演进最小栈的变体在面试中远比原题常见我至少见过三种变形最大栈把辅助栈里维护的逻辑从min换成max代码几乎对称。这个变体本身没难度但它常作为热身题出现后面会接更大强度的题目。O(1)求最小值的队列经典组合题。原理是用两个最小栈A、B模拟队列入队push到A出队时若B为空就把A的元素全部倒入B再pop B。队列的最小值是min(A.getMin(), B.getMin())前提是两个栈都改造成最小栈。我当时实际推导过一遍发现栈倒置后元素顺序完全逆转但每个栈各自维护最小值这个性质不变所以取min时只需要看两个栈顶的min。思路清晰以后代码反而不难。支持删除指定值的最小栈这个就超出原题范围了通常需要额外配合哈希表加计数器之类的结构或者用TreeMap记录栈中元素出现次数。它考察的还是栈 状态记录的组合拳。我在刷题过程中有个体会大多数设计数据结构类的题重点不在算法复杂度上玩出多少花而在于你如何把一组操作约束组合起来让每个操作都保持既定复杂度。最小栈的辅助栈思想就是这类题最朴素的起点。4.4 一个通用的答题心法最后分享一个我后期刷题一直在用的思考习惯凡是看到题目要求O(1)返回某个聚合信息最小值、最大值、平均值先问自己一个问题——这个信息在数据被删除时还能不能O(1)得到如果答案是不能那你几乎必然需要一个历史快照结构。最小栈的快照是辅助栈LRU的快照是双向链表单调栈的快照是栈里维护的关键区间。想通了快照这件事你会发现很多题其实是同一个故事的不同版本。155题我刷过三遍第一遍背答案第二遍搞懂辅助栈第三遍想明白为什么辅助栈可行而单变量不可行。第三遍之后这道题才算真正吃透。