把 LeetCode Hot 100 里标着“栈”标签的题拎到一起刷是我刷算法题时最值得的一次整理。按专题刷下来你会发现栈题单看都不算难但合在一起正好串起括号匹配、逆波兰表达式、单调栈、二叉树非递归遍历、回溯模拟这一整条线。很多人刷栈题是零散着刷的今天做有效的括号明天做接雨水AC 完就忘但如果你把 Hot 100 里的栈题当成一个整体来看它会给你一个非常清晰的图景栈不只是一种数据结构更是一种处理“最近未决信息”的思维方式。这篇文章不打算罗列题号让你背题而是想拆一下栈题背后的共同模型讲清楚每类题为什么用栈、边界条件在哪、代码怎么写才稳。无论你是刚开始刷 Hot 100 的新手还是复习到了一半想回头梳理的老手应该都能从中拿到一些还能用的东西。1. 先看清 Hot 100 里的栈题到底在考什么1.1 栈题在 Hot 100 里的真实分布与定位Hot 100 里标着栈的题粗略分是四类。第一类是基础结构应用包括有效的括号20、最小栈155、逆波兰表达式求值150、用栈实现队列232。第二类是表达式与展开类的模拟典型的有字符串解码394、基本计算器224 / 227、简化路径71。第三类是单调栈代表题是每日温度739、下一个更大元素496、柱状图中最大的矩形84、接雨水42。第四类是栈和二叉树、递归回溯的结合比如二叉树的前序、中序、后序遍历的非递归写法144 / 94 / 145以及某些 DFS 回溯的迭代实现。这个分布很有意思真正考“栈 API 使用”的题很少更多题考的是你有没有能力把一个问题抽象成“最近未决信息”的匹配过程。比如括号匹配本质上是一个新出现的右括号必须去和“最近一次出现的、还没匹配的左括号”配对逆波兰表达式本质上是一个运算符出现时最近的几个数字才具备被计算的资格单调栈更明显你要找的是“右侧第一个比当前元素更大/更小”的信息这种信息天然带有“位置上的先后关系”。所以面试和刷题时栈题的美妙之处在于它很少和你绕弯子一旦你意识到应该用栈解题思路通常是直给。难点反而在实现细节比如栈里存的是值还是索引、while 循环里比较的是当前元素还是栈顶元素、出栈时机选在什么时候。1.2 我建议的刷题顺序先“匹配逻辑”再“单调性”如果你按 Hot 100 的题号顺序去刷20 有效的括号在最前面但 84 接雨水和 42 接雨水在很后面中间会穿插很多别的专题。按专题刷的时候我强烈建议的顺序是先做 20、155、150、232 这四道基础题把“什么时候入栈、什么时候出栈”的手感建立起来然后做 71 和 394体会字符串模拟里的栈接着再碰单调栈从 496 开始再到 739、84、42。原因是单调栈并不是一种独立的“高深算法”它是在基础栈之上增加了一个约束栈内元素按单调递增或单调递减排列。如果你连最小栈里“同步记录当前最小值”都没理解直接上手单调栈会非常容易迷失在“单调递增还是递减”的方向里。我见过不少朋友直接刷 84 柱状图看完题解说“啊原来要用单调栈”但问他为什么出栈时计算面积他答不上来那就是基础栈的思维还没建立。2. 基础栈题括号、逆波兰和最小栈的边界细节2.1 括号匹配为什么不能用计数器硬写有效的括号这题看起来像是“计数配对”问题一个左括号对一个右括号嘛。但如果只有一种括号你确实可以用一个计数器一旦括号有三种类型(、[、{问题就变了你不仅要数量匹配还要顺序匹配。最典型的反例是([)]数量上左括号和右括号各两个但它是非法字符串。因为右括号)匹配的应该是最近未匹配的左括号[而不是最前面的(。这就是栈出现的直接原因栈的 LIFO 特性完美匹配“最近的未决项”这个语义。遇到左括号就入栈遇到右括号时栈顶元素必须是对应的左括号如果不是直接返回 false最后还要检查栈是不是为空。def isValid(s: str) - bool: pairs {): (, ]: [, }: {} stack [] for ch in s: if ch in pairs: if not stack or stack[-1] ! pairs[ch]: return False stack.pop() else: stack.append(ch) return not stack这段代码里有三个最容易踩的坑。第一右括号来的时候先判空比如字符串是]一上来就 pop 肯定越界但更重要的是语义上它根本没有左括号可以匹配。第二比较的是栈顶和当前右括号对应的左括号不是把当前右括号入栈。第三循环结束要返回not stack因为可能字符串是(()左括号多出来了。2.2 最小栈空间换时间的关键是“同步压栈”最小栈这题有个很经典的约束要求 getMin 在 O(1) 时间内返回栈中的最小元素。如果你每次 getMin 都遍历一遍那就没意义了。所以主流方案是再加一个辅助栈专门记录“当前栈状态下的最小值”。很多题解叫它“双栈法”但我觉得更准确的说法是“同步维护法”。主栈 push 一个值 x 时辅助栈也 push 一个值这个值等于min(x, 辅助栈栈顶)。主栈 pop 时辅助栈同步 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) 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]我见过不少人写的简化版本是辅助栈只在“新最小值出现时”才 pushpop 时判断如果主栈弹出的值等于辅助栈栈顶就同步弹出。这个版本也能 AC而且省空间但它有个麻烦如果有重复最小值pop 判断要特别小心否则辅助栈被多弹一次或漏弹一次。新手我更推荐上面这种“同步压栈”版本逻辑最直白不出错。空间上多花 O(n)换回来的是无脑的稳定性值得。2.3 逆波兰表达式与中缀表达式优先级处理的本质逆波兰表达式求值150是最直观的栈应用遇到数字就入栈遇到运算符就弹出两个数计算结果再把结果压回栈里。但这里有两个细节特别容易翻车。第一个是减法和除法的操作数顺序。弹出两个数先弹出的是右操作数后弹出的是左操作数。比如表达式[4, 13, 5, /, ]当遇到/时第一次 pop 出 5第二次 pop 出 13计算的是13 / 5不是5 / 13。第二个是除法要处理负数截断方向C 和 Python 的取整规则不一样LeetCode 要求向零截断所以 Python 里要写成int(a / b)而不能直接用a // b因为-3 // 2 -2而int(-3 / 2) -1。当你理解了逆波兰怎么算再看 Hot 100 里的基本计算器224 / 227就会明白它其实是逆波兰的逆问题给你中缀表达式你要自己把运算符优先级理清楚。常见的实现是“双栈”一个数字栈一个运算符栈。遇到数字入数字栈遇到运算符时如果当前运算符优先级不高于栈顶运算符就先弹出栈顶运算符计算遇到左括号直接入运算符栈遇到右括号则一直弹出计算到左括号为止。# 227. 基本计算器 II 的核心骨架只含 - * / def calculate(s: str) - int: num_stack [] op num 0 for i, ch in enumerate(s): if ch.isdigit(): num num * 10 int(ch) if ch in -*/ or i len(s) - 1: if op : num_stack.append(num) elif op -: num_stack.append(-num) elif op *: num_stack.append(num_stack.pop() * num) else: num_stack.append(int(num_stack.pop() / num)) op ch num 0 return sum(num_stack)这个“边扫边压边算”的思路非常重要。它没有显式运算符栈因为它用了“看到下一个运算符再结算前一个运算符”的技巧本质上还是栈的后进先出在发挥作用。前程无忧地讲这一块的灵魂是优先级高的运算要尽可能先做而“先做”的顺序需要后进先出的容器来维护。3. 单调栈一类题的骨架就是这么简单3.1 单调栈维护的不是“元素”而是“候选答案”单调栈是我在 Hot 100 里认为最值得单独拎出来讲的类型。很多人一上来就被“单调递增栈”“单调递减栈”这两个词劝退其实它的本质很简单保证栈里的元素按某种单调性排列每次新元素入栈前把破坏单调性的栈顶元素弹出。弹出的时候往往就是计算某个答案的时机。以“下一个更大元素”为例。假设数组[2, 1, 5, 6, 2, 3]你从左往右遍历想找每个元素右边第一个比它大的值。最朴素的做法是双重循环O(n^2)。但如果你用一个“从栈底到栈顶单调递减”的栈遇到新元素 x 时如果 x 大于栈顶元素说明栈顶元素的“下一个更大元素”已经出现了就是 x于是弹出栈顶并记录答案如果 x 小于等于栈顶就把 x 入栈因为它可能是栈内元素的答案。这时候栈里存的其实是“还没找到答案的元素的索引”它们彼此维持单调递减等着某个更大的未来元素来把它们一个个捞走。def nextGreaterElement(nums): n len(nums) ans [-1] * n stack [] for i in range(n): while stack and nums[stack[-1]] nums[i]: idx stack.pop() ans[idx] nums[i] stack.append(i) return ans这个模板值得背但比背诵更重要的是为什么弹栈时就是答案因为从当前栈顶 idx 被压入到被弹出的这一刻之间所有元素都小于等于nums[idx]否则它们会先把 idx 弹出去因此当前元素nums[i]是 idx 右边第一个大于它的值。单调栈用 O(n) 时间换掉了 O(n^2) 的重复扫描代价是每个元素最多入栈一次、出栈一次。3.2 每日温度和下一个更大元素同一个模板的两种问法Hot 100 里的每日温度739其实就是“下一个更大元素”的孪生题给你一组温度返回每个位置要等几天才会出现更高的温度。解法一模一样唯一区别是返回的不是“更大元素的值”而是“两个索引之间的距离”。def dailyTemperatures(temperatures): n len(temperatures) ans [0] * n stack [] for i in range(n): while stack and temperatures[stack[-1]] temperatures[i]: idx stack.pop() ans[idx] i - idx stack.append(i) return ans你会看到代码结构几乎没变只是ans[idx] nums[i]换成了ans[idx] i - idx。这就是我刚才强调“栈里存索引、不存值”的原因如果你在栈里存温度值等你弹出时你根本不知道这个温度出现的位置距离就无法计算。这个经验可以推广到所有单调栈题存索引比较值。还有一类从右往左遍历的写法我在这里提一句。从右往左时栈里存的是“右边还没解决的元素”模板会变成def nextGreaterElement(nums): n len(nums) ans [-1] * n stack [] for i in range(n - 1, -1, -1): while stack and nums[stack[-1]] nums[i]: stack.pop() ans[i] nums[stack[-1]] if stack else -1 stack.append(i) return ans两种写法没优劣之分但你要固定一种别在考场上混着用。我个人习惯从左往右因为出栈时直接结算答案思路更符合“未来到来”的时间流。3.3 84 和 42矩形面积与雨水单调栈的两种出栈时机如果说前面的单调栈只是套模板那么 84 柱状图中最大的矩形和 42 接雨水就要开始“扣细节”了。这两题是 Hot 100 里栈专题天花板级别的存在但它们的核心思路却惊人的对称。柱状图最大矩形84维护的是一个从栈底到栈顶单调递增的栈。遍历到柱子 i如果heights[i]小于栈顶柱子高度说明栈顶柱子的右边界已经出现因为在它右边已经有一个比它矮的柱子矩形的右边界不可能再扩展。于是弹出栈顶h此时新的栈顶就是左边界矩形宽度是i - left - 1面积是h * width。def largestRectangleArea(heights): # 首尾补0方便处理递增/递减边界 heights [0] heights [0] stack [] ans 0 for i, h in enumerate(heights): while stack and heights[stack[-1]] h: height heights[stack.pop()] left stack[-1] ans max(ans, height * (i - left - 1)) stack.append(i) return ans首尾补 0 这个操作是实战里的关键。如果整个数组单调递增比如[2, 3, 4]那永远不会触发弹栈面积算不出来补一个 0 在最右边就强制把栈弹空。左边补 0是防止弹到栈空时left不存在。接雨水42恰好维护的是单调递减栈。遍历到柱子 i如果heights[i]大于栈顶柱子高度说明栈顶柱子形成了一个凹槽底部可以接水。弹出栈顶后新的栈顶是左侧更高的柱子当前柱子是右侧更高的柱子两侧高度中的最小值减去凹槽高度乘以左右边界之间的距离就是这一层的水量。def trap(height): ans 0 stack [] for i, h in enumerate(height): while stack and height[stack[-1]] h: bottom stack.pop() if not stack: break left stack[-1] width i - left - 1 bounded_height min(height[left], h) - height[bottom] ans width * bounded_height stack.append(i) return ans这里特别容易混淆方向矩形面积是遇到更矮时弹栈结算接雨水是遇到更高时弹栈结算。为什么反了因为矩形要“向左找比自己矮的边界”所以栈内保持递增雨水要“找左右比自己都高的柱子去夹住当前柱”所以栈内保持递减。你不需要死记“递增还是递减”而是每次弹栈前问自己当前柱子是让栈顶出栈的“右边界”那我要计算的答案依赖的是左侧哪个量想清楚这一点单调栈就不玄了。4. 栈回溯递归是隐式调用栈显式栈才是可控的解4.1 backtrace 栈回溯到底是什么意思标题里看到“backtrace 栈回溯”这个词很多人的第一反应是“递归回溯”。这个词本身其实包含了计算机组成原理里的调用栈概念函数每递归一层系统就压一个栈帧进去返回值、局部变量全在栈帧里递归返回时栈帧弹出状态自然恢复到上一层。所以“回溯”这个词和“栈”是深度绑定的。在 Hot 100 的栈题里最直接的例子是字符串解码394。比如3[a2[c]]当你扫描到[时你需要把当前的上下文压入栈扫描到]时再从栈里弹出来恢复上下文。这个过程和函数递归一模一样[相当于函数的开始]相当于函数返回。def decodeString(s: str) - str: stack [] cur_str cur_num 0 for ch in s: if ch.isdigit(): cur_num cur_num * 10 int(ch) elif ch [: stack.append((cur_str, cur_num)) cur_str, cur_num , 0 elif ch ]: prev_str, num stack.pop() cur_str prev_str cur_str * num else: cur_str ch return cur_str这里的“入栈”就是在保存现场“出栈”就是在恢复现场。你能直观看到字符串解码如何利用栈的 LIFO 结构处理嵌套括号。理解了这一点再去看各种递归回溯题目会发现它们的灵魂都是同一个东西进入子状态前压栈子状态结束后弹栈回到父状态。4.2 二叉树遍历的非递归写法把每个递归都翻译成栈Hot 100 里有好几道二叉树遍历题可以用递归秒掉但面试官常常追问“能不能非递归”。非递归的本质就是用显式栈模拟系统调用栈。前序遍历最简单因为访问顺序天然适合栈先把根入栈然后每次弹出节点访问它再先把右孩子入栈、后把左孩子入栈这样左孩子会先出栈被访问。def preorderTraversal(root): res [] stack [root] while stack: node stack.pop() if not node: continue res.append(node.val) stack.append(node.right) stack.append(node.left) return res中序遍历稍微复杂一点因为要先一直往左走把沿途节点压栈直到没有左孩子再弹出节点访问然后转向右子树。很多人卡在中序遍历就是没意识到“一路向左入栈”其实是在模拟递归函数中先调用dfs(root.left)的行为。后序遍历的迭代写法有几种我比较喜欢“反过来”的思路先按根、右、左的顺序做一次先序遍历最后把结果反转因为后序遍历是左、右、根先序变体倒过来就是。这样避免双栈的繁琐实际写起来也快。4.3 显式栈带来的额外收益避免递归爆栈递归和显式栈在算法逻辑上是等价的但在运行环境里有一个重要差异递归深度受系统调用栈限制。Python 默认递归深度大约 1000 层再深就会RecursionError而显式栈用的是堆内存空间只要你内存够能处理更大的深度。所以当题目给的二叉树是一条链、树高可能到了上万层时显式栈就不只是“面试炫技”而是工程上的必需品。Hot 100 里虽然很少出现这种极端数据但在实际项目里遍历超深目录、解析嵌套 JSON、渲染深层 UI 树时我都踩过递归爆栈的坑。所以刷栈题时我建议你把每一道递归能做的题至少尝试用显式栈写一遍。不是为了炫技是为了让你在真正需要控制调用栈的地方能拿得出方案。5. 栈与队列、堆栈对比别让概念混淆干扰解题5.1 用栈实现队列与用队列实现栈容器思维的转换Hot 100 里的“用栈实现队列”232是一道很经典的思维题。栈是 LIFO队列是 FIFO两个方向相反。要用栈实现队列核心是“倒两次就正过来了”一个输入栈、一个输出栈。push 的时候往输入栈压pop 的时候如果输出栈为空把输入栈全部倒入输出栈这时元素的顺序就反过来了输出栈的栈顶就是最早入队的元素。class MyQueue: def __init__(self): self.in_stack [] self.out_stack [] def push(self, x: int) - None: self.in_stack.append(x) def pop(self) - int: if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop()) return self.out_stack.pop() def peek(self) - int: if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop()) return self.out_stack[-1] def empty(self) - bool: return not self.in_stack and not self.out_stack这里有一个非常重要的摊还分析虽然某一次 pop 可能要倒一整批元素但每个元素最多从 in_stack 搬到 out_stack 一次所以整体均摊时间复杂度是 O(1)。这也是为什么很多帖子里说“232 是理解均摊复杂度的最佳入门题”。反过来用队列实现栈225就要用“旋转法”。每次 push 时先把新元素入队然后弹出队尾之前的所有元素重新入队让新元素跑到队首这样队首就是栈顶pop 时直接出队。这两种题对比着做你会明显感受到栈和队列只是访问顺序不同的容器算法题考察的是你如何用容器组合去改变数据的流动顺序。5.2 堆和栈在算法里的两个世界“堆和栈”这个热词在算法题里特别容易造成误解。刷题时说的“堆”是堆数据结构通常指优先队列对应 TopK、合并 K 个有序链表、数据流中位数那类题而“栈”是 LIFO 顺序结构对应的是括号、表达式、单调栈。两者八竿子打不着。但到了程序运行时的内存模型里“堆”是动态分配内存的区域“栈”是函数调用帧的存放区域。同一个词在不同语境下意思完全不同。你不需要背操作系统的内存分区细节才能刷题但是有一个点和高频题是挂钩的递归函数跑太深会爆栈。为什么叫“栈溢出”因为每次函数调用都要在系统栈上压一个栈帧递归不返回栈帧就一直在累积直到超过系统限制。这就是我们在第四章说的显式栈方案的价值。还有一个小提醒C 里std::stack默认底层容器是std::dequeJava 的Stack类本身是Vector子类性能上不如ArrayDeque所以 Java 刷题更推荐DequeInteger stack new ArrayDeque();。这些语言细节看起来琐碎但真到面试写白板代码时能不能写出“符合现代规范”的栈用法也是加分项。6. 按难度递进的栈刷题路线和实测调试心得6.1 我自己试过的一条路线表如果你现在打开 Hot 100 准备按栈专题刷我给一份可以照抄的顺序。它把难度分成四档每档内部建议完成再进入下一档。阶段题目核心考点完成标志基础20 有效的括号栈匹配模型能写出括号 map 版本考虑栈空基础155 最小栈辅助栈同步维护能解释为什么 pop 不会漏基础150 逆波兰表达式操作数顺序能处理除法向零取整基础232 用栈实现队列双栈倒换能说明摊还 O(1)字符串71 简化路径字符串按分隔符解析能处理.和..的边界字符串394 字符串解码括号嵌套展开能秒答3[a2[c]]单调栈496 下一个更大元素 I单调栈模板能写出从左往右版本单调栈739 每日温度索引差值能解释为什么存索引单调栈84 最大矩形递增栈哨兵知道首尾补 0 的用途单调栈42 接雨水递减栈按层结算能区分 84 和 42 的弹栈方向二叉树144、94、145 遍历显式栈模拟递归能写出三种迭代遍历高级224 / 227 基本计算器双栈处理优先级能处理带括号的表达式这个表不是为了让你一次性全刷完。我的建议是基础档两天内搞定字符串档配合正则或者手动模拟多写几遍单调栈档是重头至少安排一周每天只写 1-2 道并且每一道题都动手跑几个例子。6.2 调试单调栈的通用技巧单调栈题 debug 最有效的方法不是看题解而是打印栈。每次入栈、出栈都打印当前索引、当前值、栈内索引列表和栈内值列表。我举个常用调试思路for i, h in enumerate(heights): while stack and heights[stack[-1]] h: idx stack.pop() print(pop idx, idx, value, heights[idx], current h, h) # 结算面积 stack.append(i)你会发现只要在几个关键弹栈位置打印所有边界条件都会变得很清楚。比如 84 题你能直观看到一个凹槽是怎么形成的栈内高度递增排列遇到一个更矮的柱子时栈顶已经在等待右边界了而当前柱子就是那个“终结者”。另一个通用技巧是手跑样例时要在代码旁边写下“栈里存的到底是什么”。很多同学写单调栈时把自己绕晕就是因为栈里一会儿存值一会儿存索引搞不清比较的对象。统一做法是栈里只存索引比较时写nums[stack[-1]]结算时如果需要值就再用索引取。这个习惯能避免至少一半的 bug。6.3 容易被忽略的三个边界错误第一个错误是弹栈前不检查栈空。接雨水 42 里弹出凹槽底部后如果栈空了说明左边没有更高的柱子无法形成水洼这时候要break或跳过结算。很多人一开始会试图用if not stack: return之类来处理但实际题目只是“这一层没法接水”而不是整体结束。第二个错误是混淆“严格大于”和“大于等于”。84 最大矩形中遇到相等高度时到底弹不弹栈顶严格说高度相等时弹出并不会算错因为算出来的面积相同但会多几次无效计算如果你用“大于等于”的写法也没问题。最容易出错的是 739 每日温度遇到相等温度不能弹栈因为题目要求“更高的温度”严格大于才算。所以在单调栈的 while 条件里一定要想清楚题目的语义是“下一个更大”还是“下一个不小于”。第三个错误是忘记返回的是距离还是值。739 返回距离496 返回值题目改一个字答案就差很多。我强烈建议每道题 AC 之后把代码中的结算行改成另一种问法再写一遍比如把“温度距离”改成“输出温度值”。这个练习会让你意识到单调栈模板的变体是怎么发生的。最后再分享一个小技巧刷栈专题的时候不要只满足于 AC多想想这题如果限制不能用栈能不能做。比如括号匹配用计数器行不行接雨水能不能用双指针。这种对比不只是在拓宽解法也是在帮你确认“什么时候栈是唯一合理的工具”。等你能在一道新题里快速判断“这里该用栈”Hot 100 里的栈题就算真正吃透了。