题目描述
思路解析
一句话答案：LeetCode 155 最小栈的标准解法是辅助栈：主栈正常存数据，辅助栈与主栈同步压弹、每层存「压入这层之后整栈的最小值」，push 时压入 min(新元素, 辅助栈顶)，pop 时两栈同弹。getMin 直接读辅助栈顶，push、pop、top、getMin 全部 O(1)，代价是 O(n) 的额外空间。
这道题真正在问什么
设计一个栈，除了常规的 push、pop、top，还要提供 getMin——在常数时间内返回栈中当前的最小元素。难点全在「常数时间」四个字：栈里的内容随压弹不断变化，最小值也跟着变，getMin 却不许现场遍历去找。这是一道考「用空间换时间、为查询预留答案」的设计题。
为什么一个最小值变量不够用
最直觉的偷懒办法是维护一个变量 min，push 时顺手更新。压栈没问题，坏在 pop：一旦弹出的恰好是当前最小值，min 该回退成「剩下元素里的最小值」——可这个值是多少，单个变量没有记录，只能重新遍历整个栈去找，O(1) 就破功了。
这暴露了问题的真正需求：我们需要的不是「一个最小值」，而是「每个历史时刻的最小值」，弹栈时才能随时回退到上一个状态。历史状态要跟着栈的压弹同步存取——后压的状态先失效——这本身又是一个后进先出的过程，所以答案呼之欲出：再用一个栈来存最小值的历史。
辅助栈的不变量怎么定义
开一个辅助栈 mn，与主栈 st 保持两条不变量：一是高度永远相等，二是 mn 的第 i 层存「主栈从栈底到第 i 层这一段的最小值」。于是 mn 的栈顶恒等于当前整个主栈的最小值，getMin 读一下栈顶就完事。
维护也只要两条同步规则。push(x) 时：主栈压 x，辅助栈压 min(x, mn 栈顶)——新最小值要么是 x 自己，要么延续原来的最小值；辅助栈为空时直接压 x。pop 时：两栈同时弹一个。注意辅助栈压的是取 min 之后的结果而不是 x 本身，压 x 本身的话栈顶就不再代表全栈最小，整个设计就塌了。
为什么 pop 之后最小值自动恢复正确
关键在于辅助栈每一层的含义是「截至这一层的前缀最小值」，它只由主栈更低的那些层决定，与后来压入的元素无关。弹掉栈顶后，露出来的新栈顶记录的正是「剩余那些元素的最小值」——这个答案在当初压栈时就算好存在那里了，弹栈只是把它重新露出来，不需要任何补算。
这就是本题的核心思想：与其在查询时现找答案，不如在每次入栈时把「此刻的答案」一并存档，出栈时档案随之销毁，任何时刻栈顶档案都与栈内容严格对应。
复杂度怎么算，有哪些进阶变体
四个操作 push、pop、top、getMin 都只做常数次栈操作，时间各是 O(1)；辅助栈与主栈一样高，额外空间 O(n)。
空间上有两个常见优化方向：一是辅助栈只在新元素小于等于栈顶时才压入，弹栈时判断相等才同步弹，能省掉大量重复的最小值，但相等情形的处理容易写错；二是「差值法」，主栈存 x 与当前最小值的差、外加一个 min 变量，能把额外空间压到 O(1)，代价是要处理编码解码和数值溢出。面试先把基础辅助栈讲清楚，再提这两个变体作为亮点即可。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
核心思路：辅助栈 mn 与主栈 st 高度永远相等。mn 的栈顶，始终是「当前主栈里所有元素的最小值」。
push(x)：主栈压 x，辅助栈压 min(x, 辅助栈原栈顶)。pop：两栈同时弹一个。这样辅助栈顶恒为最小值。
先看初始状态：主栈和辅助栈都为空。接下来每次 push 两栈同步压入，每次 pop 两栈同步弹出，高度始终相等。
push(-2)：主栈压入 -2；辅助栈压入 -2（栈空，直接放） = -2。两栈同时长高一格，辅助栈顶 -2 就是现在主栈的最小值。
push(0)：主栈压入 0；辅助栈压入 min(0, 辅助栈顶-2) = -2。两栈同时长高一格，辅助栈顶 -2 就是现在主栈的最小值。
push(-3)：主栈压入 -3；辅助栈压入 min(-3, 辅助栈顶-2) = -3。两栈同时长高一格，辅助栈顶 -3 就是现在主栈的最小值。
getMin()：直接读辅助栈顶 -3，O(1) 拿到当前主栈最小值，完全不用遍历主栈。
pop()：主栈和辅助栈同时弹掉栈顶（弹出主栈的 -3）。两栈高度依旧相等，弹完后辅助栈顶 = -2，自动回退到上一个最小值。
top()：返回主栈顶 0。辅助栈只管最小值，不影响 top。
getMin()：直接读辅助栈顶 -2，O(1) 拿到当前主栈最小值，完全不用遍历主栈。
push(5)：主栈压入 5；辅助栈压入 min(5, 辅助栈顶-2) = -2。两栈同时长高一格，辅助栈顶 -2 就是现在主栈的最小值。
push(-1)：主栈压入 -1；辅助栈压入 min(-1, 辅助栈顶-2) = -2。两栈同时长高一格，辅助栈顶 -2 就是现在主栈的最小值。
push(-4)：主栈压入 -4；辅助栈压入 min(-4, 辅助栈顶-2) = -4。两栈同时长高一格，辅助栈顶 -4 就是现在主栈的最小值。
getMin()：直接读辅助栈顶 -4，O(1) 拿到当前主栈最小值，完全不用遍历主栈。
pop()：主栈和辅助栈同时弹掉栈顶（弹出主栈的 -4）。两栈高度依旧相等，弹完后辅助栈顶 = -2，自动回退到上一个最小值。
top()：返回主栈顶 -1。辅助栈只管最小值，不影响 top。
push(-4)：主栈压入 -4；辅助栈压入 min(-4, 辅助栈顶-2) = -4。两栈同时长高一格，辅助栈顶 -4 就是现在主栈的最小值。
getMin()：直接读辅助栈顶 -4，O(1) 拿到当前主栈最小值，完全不用遍历主栈。
pop()：主栈和辅助栈同时弹掉栈顶（弹出主栈的 -4）。两栈高度依旧相等，弹完后辅助栈顶 = -2，自动回退到上一个最小值。
getMin()：直接读辅助栈顶 -2，O(1) 拿到当前主栈最小值，完全不用遍历主栈。
pop()：主栈和辅助栈同时弹掉栈顶（弹出主栈的 -1）。两栈高度依旧相等，弹完后辅助栈顶 = -2，自动回退到上一个最小值。
pop()：主栈和辅助栈同时弹掉栈顶（弹出主栈的 5）。两栈高度依旧相等，弹完后辅助栈顶 = -2，自动回退到上一个最小值。
pop()：主栈和辅助栈同时弹掉栈顶（弹出主栈的 0）。两栈高度依旧相等，弹完后辅助栈顶 = -2，自动回退到上一个最小值。
getMin()：直接读辅助栈顶 -2，O(1) 拿到当前主栈最小值，完全不用遍历主栈。
pop()：主栈和辅助栈同时弹掉栈顶（弹出主栈的 -2）。两栈高度依旧相等，弹完后辅助栈顶 = （空），自动回退到上一个最小值。
push(6)：主栈压入 6；辅助栈压入 6（栈空，直接放） = 6。两栈同时长高一格，辅助栈顶 6 就是现在主栈的最小值。
push(3)：主栈压入 3；辅助栈压入 min(3, 辅助栈顶6) = 3。两栈同时长高一格，辅助栈顶 3 就是现在主栈的最小值。
push(9)：主栈压入 9；辅助栈压入 min(9, 辅助栈顶3) = 3。两栈同时长高一格，辅助栈顶 3 就是现在主栈的最小值。
push(1)：主栈压入 1；辅助栈压入 min(1, 辅助栈顶3) = 1。两栈同时长高一格，辅助栈顶 1 就是现在主栈的最小值。
getMin()：直接读辅助栈顶 1，O(1) 拿到当前主栈最小值，完全不用遍历主栈。
pop()：主栈和辅助栈同时弹掉栈顶（弹出主栈的 1）。两栈高度依旧相等，弹完后辅助栈顶 = 3，自动回退到上一个最小值。
pop()：主栈和辅助栈同时弹掉栈顶（弹出主栈的 9）。两栈高度依旧相等，弹完后辅助栈顶 = 3，自动回退到上一个最小值。
pop()：主栈和辅助栈同时弹掉栈顶（弹出主栈的 3）。两栈高度依旧相等，弹完后辅助栈顶 = 6，自动回退到上一个最小值。
top()：返回主栈顶 6。辅助栈只管最小值，不影响 top。
getMin()：直接读辅助栈顶 6，O(1) 拿到当前主栈最小值，完全不用遍历主栈。
最后再 push(7) 收个尾：主栈与辅助栈又同步长高一格，辅助栈顶 7 即此刻最小值。规律始终是「两栈同步、辅助栈顶即最小」。
边界都围绕「空栈」和「重复最小值」，辅助栈同步压入能正确处理重复。
两个高频追问：O(1) 空间的差值法、辅助栈去重优化，作为进阶加分项。
参考代码
class MinStack: def __init__(self): self.st = [] # 主栈 self.mn = [] # 辅助栈：同步存最小值 def push(self, x: int) -> None: self.st.append(x) m = x if not self.mn else min(x, self.mn[-1]) self.mn.append(m) # 压入 min(x, 辅助栈顶) def pop(self) -> None: self.st.pop() self.mn.pop() # 两栈同步弹 def top(self) -> int: return self.st[-1] def getMin(self) -> int: return self.mn[-1] # O(1)：辅助栈顶即最小值复杂度
- 时间：O(1) / 操作，push/pop/top/getMin 都是常数次栈操作
- 空间：O(n)，辅助栈和主栈一样高，额外 O(n)
易错点
面试追问把动画讲成自己的话
追问能不能不用辅助栈、只用 O(1) 额外空间？
追问辅助栈里存重复的最小值会不会浪费？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
逆波兰表达式求值
LeetCode 150 · 中等 · 沿着 栈 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题