先交代个背景最近我二刷 LeetCode 热题 100刷到一半发现一个很有意思的现象——栈相关的好几道经典题其实是一条线串下来的。今天想详细聊聊其中三道394 字符串解码、739 每日温度、84 柱状图中的最大矩形。这三道题单独看各有各的难点但放在一起看你会发现它们恰好覆盖了栈的三种典型用法延迟组装、单调性维护、边界归一化。把这个思路理顺以后再碰栈相关的题思路会清晰很多。1. 为什么把这三道题放在一起它们正好踩在栈的三种典型用法上先说说我最初刷这三道题的感受。394 字符串解码第一次见会有点懵因为它在括号嵌套里玩字符串拼接规则多、状态杂739 每日温度看着简单但暴力解法一写出来就知道肯定超时84 柱状图中的最大矩形就更头疼了很多人一开始连暴力枚举的方向都找不到。但如果你把解题过程里栈到底在干嘛这件事单独拎出来看会发现三者的差异非常清晰题号题目栈的角色核心难点394字符串解码辅助栈暂存外层数据和字符串嵌套括号时如何恢复现场739每日温度单调递减栈记录待匹配下标为什么栈里存的是下标而不是温度84柱状图中的最大矩形单调递增栈结算矩形面积左右边界如何确定哨兵怎么用这个顺序本身也是一个难度递进的过程394 只要理解遇到左括号就入栈、遇到右括号就出栈就能写出来739 需要你理解单调性这个概念知道什么时候该弹出栈顶84 则是把单调栈的边界处理做到了极致不把哨兵技巧想明白写出来的代码要么栈空越界要么最后漏算。所以这篇文章我会按这个顺序展开最后再把这些题串成一个统一的思考框架。每道题我都会给完整的 Python 代码、手算推演过程、以及我实际写代码时踩过的坑。2. 字符串解码394一次遍历把嵌套括号拆干净2.1 核心思路辅助栈与延迟组装题目长这样给定一个编码字符串比如3[a2[c]]要解码成accaccacc。规则是数字[字符串]表示方括号里的字符串重复数字次而且括号可以嵌套。我第一次看到这题的时候第一反应是递归遇到[就递归处理处理完返回字符串和新的下标。这个思路没问题但写起来每一步都要小心翼翼地维护下标非常容易错。相比之下用辅助栈的迭代写法更直观而且不需要额外处理递归深度问题。核心思想一句话概括把还没处理完的前缀字符串和重复次数先存起来等内层括号算完再取出来拼接。这就好比你在做多层嵌套的收纳盒先把外面的东西放一边把最里面的东西拿出来组装好再一层一层往外装回去。具体做法是维护两个栈一个数字栈num_stack一个字符串栈str_stack再用两个变量cur_num和cur_str记录当前正在积累的数字和字符串遇到数字时累加到cur_num注意数字可能不止一位要按cur_num cur_num * 10 int(ch)累积。遇到字母时直接追加到cur_str。遇到[表示要进入下一层把当前cur_num和cur_str压栈然后把它们清零开始处理内层。遇到]表示内层结束弹出数字和前缀字符串把当前cur_str重复数字次再拼到前缀后面。2.2 完整代码与逐步推演def decodeString(s: str) - str: num_stack [] str_stack [] cur_num 0 cur_str for ch in s: if ch.isdigit(): cur_num cur_num * 10 int(ch) elif ch [: num_stack.append(cur_num) str_stack.append(cur_str) cur_num 0 cur_str elif ch ]: num num_stack.pop() pre_str str_stack.pop() cur_str pre_str cur_str * num else: cur_str ch return cur_str我用3[a2[c]]手算一遍大家感受一下这个状态切换的过程当前字符cur_numcur_str栈内状态33空[0num[3], str[]a0anum[3], str[]22anum[3], str[][0num[3,2], str[, a]c0cnum[3,2], str[, a]]0ccnum[3], str[]]0accaccacc空注意看倒数第二步遇到第一个]时弹出num2和pre_stra当前cur_strc拼接结果a c*2 acc。紧接着遇到第二个]弹出num3和pre_str拼接结果 acc*3 accaccacc。这就是嵌套括号的处理逻辑越内层的字符串越先被展开然后作为外层的当前字符串参与下一次拼接。2.3 三个容易出错的坑这个解法代码很短但有三个细节我实际写的时候反复错过。第一个坑是数字累加。一开始不少人写成cur_num int(ch)遇到12[abc]这种就废了数字被拆成1和2。正确做法是每遇到一个数字字符就乘 10 再加当前位直到遇到[才把完整的数压进数字栈。第二个坑是拼接顺序。pre_str cur_str * num这个顺序不能反过来。你可以想象一下解码结果应该把外层前缀放在最前面内层展开的结果放在后面。如果写成cur_str * num pre_str那么3[a]会得到aa而不是aaa吗不会但一旦出现2[ab]3[cd]这类同一层有多个独立片段的情况顺序错了结果就完全乱了。所以记住先取回前缀再把当前层展开的结果追加到前缀后面。第三个坑是遇到[之后要记得清空状态。如果不把cur_num和cur_str清零下一层的内容会跟上一层混在一起。这个错误非常隐蔽因为小样例可能碰巧能过但嵌套一复杂就出错。3. 每日温度739单调栈模板题重点理解下标才是答案3.1 为什么暴力解法容易超时单调栈到底省在哪题目很简单给出每天的温度数组temperatures返回一个数组第i个元素表示要等多少天才会出现比第i天更高的温度如果之后没有更高温度就是 0。比如[73,74,75,71,69,72,76,73]输出[1,1,4,2,1,1,0,0]。最直观的暴力做法是每天都往后扫一遍找第一个更高温度最坏情况是温度一直递减比如[5,4,3,2,1]每一天都要扫描到数组末尾时间复杂度 O(n²)在 LeetCode 上直接超时。单调栈的做法巧妙在哪它维护的是一个从栈底到栈顶温度单调递减的下标栈。遍历过程中只要当前温度比栈顶下标对应的温度高就说明栈顶那天的下一个更高温度找到了可以弹出结算否则说明还没找到下标继续入栈等待。为什么栈里存的是下标而不是温度因为题目问的是几天后答案天然是一个距离量你需要在弹出时用当前下标 - 栈顶下标来计算天数。如果只存温度值弹出时根本算不出天数还得额外维护一个下标映射纯属给自己找麻烦。这是单调栈类题目一个非常通用的判断标准答案要什么栈里就存什么。3.2 代码实现与细节def dailyTemperatures(temperatures: list[int]) - list[int]: n len(temperatures) ans [0] * n stack [] for i in range(n): while stack and temperatures[i] temperatures[stack[-1]]: idx stack.pop() ans[idx] i - idx stack.append(i) return ans我用手算一个小例子验证[73,74,75,71,69,72,76,73]i0栈空73 入栈。此时栈[0]i174 73弹出下标 0ans[0]1然后 1 入栈。栈[1]i275 74弹出 1ans[1]1然后 2 入栈。栈[2]i371 75不弹3 入栈。栈[2,3]i469 714 入栈。栈[2,3,4]i572 69弹出 4ans[4]172 71弹出 3ans[3]272 75停。5 入栈。栈[2,5]i676 72弹出 5ans[5]176 75弹出 2ans[2]46 入栈。栈[6]i773 767 入栈。栈[6,7]最后栈里剩下的6和7对应的温度后面没有更高值答案保持初始化的 0。整个过程每个下标最多入栈一次、出栈一次整体是均摊 O(n)。3.3 两个容易忽略的地方第一个是严格大于才弹出。题目语义是更高温度所以必须用如果用会导致结果虽然在某些情况下碰巧一样但语义上不对。例如[73,73]用时第二个 73 不会弹出第一个 73两者答案都是 0用会弹出下标 0 然后算出 ans[0]1但第二天温度更高吗并不是仅仅是持平。这就是错误答案。第二个是栈底的残留元素不需要处理。因为初始化的 ans 全是 0那些从未被弹出的下标天然就是 0不用在遍历结束之后再循环遍历栈去赋值。这个小优化能让代码更简洁。4. 柱状图中的最大矩形84单调栈最难的一题哨兵技巧让边界归零4.1 暴力枚举的两个方向以及为什么都不行题目给一个非负整数数组heights每个元素代表一根柱子的高度求这些柱子能组成的最大矩形面积。注意矩形必须是一段连续柱子且矩形的高受限于这段区间里最矮的那根柱子。我第一次做这题的时候想的是枚举左右边界固定左边界往右扩展右边界同时记录区间最小高度然后更新面积。这个思路正确但复杂度是 O(n²)数据量一大就卡死。另一个想法是枚举每一根柱子作为矩形的高度然后向左右两边扩散直到遇到比它矮的柱子得到宽度算出面积。这个思路理论上可行但如果每次都真的向左右扩散最坏情况柱子高度递增仍然会退化到 O(n²)——每一根柱子都要一路扩散到边界。单调栈解决的就是这个每个柱子都想知道左右两边第一个更矮位置的问题。4.2 出栈时机与左右边界的推导核心思路可以这样理解遍历过程中维护一个从栈底到栈顶高度单调递增的栈。只要当前高度比栈顶高就继续入栈一旦当前高度比栈顶高度矮栈顶这根柱子就找到了它的右边界也就是当前下标而它左边界就是新的栈顶下标因为新的栈顶高度比它矮挡住了它继续向左扩散。此时以它为高的矩形可以结算了。具体到代码逻辑当heights[i] heights[stack[-1]]时弹出栈顶记录高度h heights[stack.pop()]此时矩形的宽度是i - stack[-1] - 1。为什么是减 1因为stack[-1]是左边第一个比h矮的柱子的下标i是右边第一个比h矮的柱子的下标左右都不包含所以宽度是两者之间的柱子数即i - stack[-1] - 1。但这里有个非常讨厌的问题如果柱子全部递增那么遍历结束时栈里还残留一堆柱子没有结算如果遇到特别矮的柱子把栈弹空stack[-1]还会直接取到不存在的元素报错。两件事都处理起来很麻烦。4.3 哨兵 0前后各加一个零柱子一次性解决所有边界问题我的做法是在heights数组前后各加一个 0变成一个带哨兵的数组。前面加 0保证任何柱子弹出后栈里始终至少还有一个更矮的哨兵不会出现栈空取不到stack[-1]的情况后面加 0因为 0 一定比所有正常柱子矮所以遍历结束时它会强制把所有剩余柱子全部弹出结算。def largestRectangleArea(heights: list[int]) - int: heights [0] heights [0] stack [] ans 0 for i in range(len(heights)): while stack and heights[i] heights[stack[-1]]: h heights[stack.pop()] w i - stack[-1] - 1 ans max(ans, h * w) stack.append(i) return ans这里强调一下很多资料会把入栈条件写成heights[i] heights[stack[-1]]也就是遇到相等高度时也弹出。这两种写法的区别在于等高柱子的处理。我的版本用严格小于才弹出等高时新柱子直接入栈右侧那个等高柱子结算时也能算对宽度如果换成小于等于等高的旧柱子会先被结算但宽度计算也一致。两种写法都能得到正确答案不过我个人习惯用严格小于因为这样栈里保留更多信息调试的时候比较直观。还是拿heights [2,1,5,6,2,3]手算一遍体会哨兵的价值数组加哨兵后是[0,2,1,5,6,2,3,0]。i0h0栈空入栈。栈[0]i1h2不小于 0入栈。栈[0,1]i2h1小于 2弹栈顶下标 1h2此时栈顶是 0w 2 - 0 - 1 1面积 2然后 1 不小于 0下标 2 入栈。栈[0,2]i3h5不小于 1入栈。栈[0,2,3]i4h6不小于 5入栈。栈[0,2,3,4]i5h2小于 6弹 4h6w 5 - 3 - 1 1面积 62 小于 5弹 3h5w 5 - 2 - 1 2面积 102 不小于 1停。栈[0,2,5]i6h3不小于 2入栈。栈[0,2,5,6]i7h0小于 3弹 6h3w 7 - 5 - 1 1面积 3小于 2弹 5h2w 7 - 2 - 1 4面积 8小于 1弹 2h1w 7 - 0 - 1 6面积 60 不小于 0停。栈[0,7]最大面积是 10正好对应高度 5、宽度 2 的那个矩形答案正确。最后那个i7的结算过程就是后哨兵在起作用它把之前因为数组递增而滞留在栈里的高度 3、2、1 全部强制结算了一遍。写代码的时候你要是把后哨兵去掉就得额外在循环结束后再处理一遍栈内残留元素容易忘也容易算错边界。5. 三题联动的思维模型延迟匹配、单调性维护、边界归一把这三道题放一起复盘会发现一个统一的解题视角栈天然适合处理现在无法立刻确定答案必须等未来信息出现后才好结算的问题。394 字符串解码里[和]就是一组延迟匹配的标记。看到[时你不知道这一层的字符串会是什么只能先把现场保存下来看到]时信息齐全了再弹出结算。这是栈最常见的配对称重用途。739 每日温度里单调递减栈维护的是一批还没遇到更高温度的下标。它们不是不能被处理而是处理时机未到——直到某一天温度升高才一口气把前面所有栈顶元素都结算掉。这就是延迟结算的典型场景。84 柱状图中的最大矩形更进一层栈维护的是高度递增的柱子序列一旦出现更矮的柱子就说明栈里那些更高的柱子已经无法继续向右扩展了右边界确定可以结算。这里不再是简单的括号配对而是需要你根据谁比谁矮来决定弹出时机同时还要自己推导左右边界公式。三个模型对应三个层次第一层延迟匹配。看到匹配符括号就想到辅助栈左右符号压栈出栈。第二层单调性维护。找下一个更大/更小就用单调栈问题答案要的是距离就存下标要的是值就存值。第三层边界归一。处理边界条件太啰嗦时加哨兵把它变成普通情况比如 84 题前后加 0链表题里常用的虚拟头节点也是同一个思路。还有一个很实用的迁移技巧碰到这类题先别急着上栈先想清楚暴力解法为什么慢然后再反推哪一步计算被重复做了、能不能延迟到某个时机一次性做完。6. 刷题复盘心得与可复用的经验这部分是我刷这三道题攒下的实战经验整理成几条希望对正在刷热题 100 的朋友有帮助。第一先手算小例子再写代码。特别是 84 题如果你没有先拿[2,1,5,6,2,3]手推一遍出栈入栈的流程直接写代码很容易在边界上卡半天。手算的过程能帮你确认栈里到底该存什么、弹出时机是什么、宽度公式怎么推导。第二栈里存什么取决于题目答案要什么。739 要的是天数距离所以存下标84 要的是面积结算时需要高度和下标所以弹出时高度从数组里取、下标从栈里取。这个判断标准套用到别的题目上也成立。比如下一个更大元素系列如果问的是元素值那栈里可以直接存值但我个人建议存下标因为通过下标能同时拿到值和位置灵活性更高。第三单调栈的均摊复杂度是 O(n)。很多人写 739 和 84 的时候看到内层有个 while 循环担心会被卡到 O(n²)。实际上每个下标只会入栈一次、出栈最多一次所以 while 循环总的执行次数是 O(n)。这一点在面试里经常被追问想清楚它为什么不是 O(n²)能体现你对算法本质的理解。第四哨兵技巧是边界处理的银弹。84 题前后加 0让我省掉了循环结束后清空栈和栈空时取不到左边界这两大麻烦。类似的思路在链表题里也很常见比如加虚拟头节点统一删除操作。多掌握这类技巧代码写出来会干净很多。第五这三道题可以当栈的配套训练一起刷。我推荐的顺序就是本文的排列字符串解码先建立延迟组装的感觉每日温度上手单调栈模板柱状图中的最大矩形再挑战边界的完整推导。刷完这三题栈相关的题目基本就有了一个稳定的思考框架再去刷接雨水最大宽度坡这类的题起码知道往哪个方向想。最后说一句个人体会栈题最迷惑人的地方就是代码看起来越短里面藏的边界条件越多。每次提交通过之前我都习惯先拿两三个极端用例自测一下——比如 394 的3[a2[c]]、739 的全递减数组、84 的全等高度数组。把这几个用例跑通了代码基本就稳了。这个习惯比看十篇题解都管用。