力扣Hot100栈专题：四道题吃透延迟处理与单调栈

力扣Hot100的栈专题，目前收录的是四道题：有效的括号、最小栈、字符串解码、每日温度。我刷完之后的一个感觉是，这四道题看起来解法各异，但底子都是同一件事——把“当时处理不了的信息”先记下来，等合适的时机再拿出来用。Java里做这件事的主要工具就是栈，而很多初学者刷完记得住代码，却说不清为什么要用栈，这正是我觉得值得写一篇总结的原因。

这类题在面试里出现频率非常高，尤其是字节、阿里这类喜欢考数据结构的公司。有效的括号是入门题，但能引出“栈顶元素与当前元素配对”的基本模型；最小栈开始加入“辅助空间”的思想；字符串解码把栈的嵌套处理能力拉到顶；每日温度则升级到单调栈，对应的是“找下一个更大/更小元素”的经典模板。四道题正好构成一条从基础到进阶的学习路径，适合按照顺序刷。

1. 栈题型的底层逻辑：为什么Hot100里栈题几乎都是“配对”与“状态保存”

1.1 栈的本质：延迟处理与最近相关性

栈这种数据结构，严格来说没什么高深的理论，就是后进先出。但很多人低估了它在算法题里的分量，尤其是“什么情况下应该想到用栈”这个判断，比会写栈操作重要得多。

我的判断标准很简单：如果一道题里，某个元素的最终答案需要等它后面的信息出现才能确定，那大概率就要用到栈。最典型的就是括号匹配，你扫描到左括号的时候，并不知道它什么时候该闭合，只能先存着，等遇到右括号再回头处理。这个“回头处理最近一个未决元素”的过程，对应的就是栈顶操作。

生活里最容易理解的例子是浏览器后退按钮，你访问A、B、C三个页面，每访问一次就压栈一次，点击后退时弹出的是C，也就是最近访问的页面。函数调用也是一样，Java里每个方法调用都会生成栈帧，方法结束后栈帧被弹出，控制权交还给调用方。算法题里的栈，本质就是把这种“最近的未完成状态”显式地表达出来。

1.2 四道题在栈手法上的关联

这四道题表面上看各有各的形态，但我们可以把它们归到四个很小的模型里：

有效的括号是“配对模型”，当前元素是右括号时，栈顶必须是对应的左括号，配对成功才弹出。

最小栈是“状态镜像模型”，除了存储数据的栈，还需要一个平行结构记录每一步的最小值，因为pop之后最小值可能变，不能只靠一个变量。

字符串解码是“嵌套恢复模型”，遇到数字和左括号，说明一个子问题开始了，当前外层状态要保存起来，等内层处理完再恢复外层拼接。

每日温度是“单调栈模型”，栈内保存的是尚未找到答案的下标，当前温度比栈顶温度高时，栈顶的答案可以被确定并弹出。

学会了这四类，往后遇到类似题就多了一层“翻译”能力。比如看到包含字母和数字的嵌套表达式，立刻想到字符串解码；看到“找到每个元素右边第一个比它大（小）的元素”这类描述，立刻切换到单调栈模板。

2. 有效的括号与最小栈：配对类题型的两种解法方向

2.1 有效的括号：栈加哈希表的标准写法与细节

题目要求判断一个只包含()[]{}的字符串是否有效，也就是括号要正确闭合、顺序要正确连接。核心思路一句话：遇到左括号就入栈，遇到右括号就检查栈顶，栈顶正好是对应的左括号则弹出，否则直接判定无效。

我在代码里习惯用HashMap建立右括号到左括号的映射，这样代码的可读性会好一些。如果用 if-else 链也能做，但四对括号还好，万一括号类型多了就不好维护。

import java.util.ArrayDeque; import java.util.Deque; import java.util.Map; class Solution { public boolean isValid(String s) { // 奇数长度的字符串不可能完全配对，直接剪枝 if (s.length() % 2 == 1) { return false; } // 用 ArrayDeque 模拟栈，不要用 Stack Deque<Character> stack = new ArrayDeque<>(); Map<Character, Character> map = Map.of( ')', '(', ']', '[', '}', '{' ); for (char c : s.toCharArray()) { if (map.containsKey(c)) { // c 是右括号，栈顶必须是对应的左括号 if (stack.isEmpty() || stack.pop() != map.get(c)) { return false; } } else { // c 是左括号，入栈等待配对 stack.push(c); } } // 最终栈为空才说明所有左括号都被匹配 return stack.isEmpty(); } }

这里有几个特别容易被忽略的细节。第一，map 里只放右括号作为 key，不要放左括号，否则判断逻辑会乱。第二，遇到右括号时栈可能为空，比如输入是"]"，这种情况直接返回 false。第三，判断栈空要在弹出之前，先弹再判就会空指针。

还有一种常见写法更简洁：遇到左括号时，把对应的右括号压入栈；遇到右括号时，弹出栈顶字符比较是否相等。这种写法的好处是不用 map，代码更短，但初读时没那么直观，适合已经熟练之后使用。

另外，实测在 LeetCode 环境下，用char[]数组模拟栈，速度比Deque快不少，内存也更省。我刷题时会先用数组模拟版本找手感，面试时再根据面试官偏好选择写法。

public boolean isValid(String s) { if (s.length() % 2 == 1) return false; char[] stack = new char[s.length()]; int top = -1; for (char c : s.toCharArray()) { if (c == '(' || c == '[' || c == '{') { stack[++top] = c; } else { if (top == -1) return false; char left = stack[top--]; if (c == ')' && left != '(') return false; if (c == ']' && left != '[') return false; if (c == '}' && left != '{') return false; } } return top == -1; }

时间复杂度是 O(n)，只需要遍历一次字符串，每个字符至多入栈一次、出栈一次，空间复杂度也是 O(n)，最坏情况字符串全是左括号。

2.2 最小栈：辅助栈的同步与非同步选择

最小栈的题目要求设计一个支持 push、pop、top、getMin 四种操作的栈结构，且 getMin 必须做到 O(1) 复杂度。很多人的第一反应是维护一个全局变量存最小值，但很快会发现，栈顶元素被弹出后，之前记录的最小值可能已经失效了。比如压入 3、1、2，全局变量记录最小值是 1，pop 掉 1 之后，整个栈里剩下的最小值变成 2，全局变量却不知道。

解决办法是保存“每个状态时刻的最小值”，而不是只保存当前一个值。最直观的做法是准备两个栈：数据栈照常存元素，辅助栈存对应状态下的最小值。push 时，数据栈正常压入 val，辅助栈压入 min(当前栈顶最小值, val)。pop 时，两个栈一起出栈。

这种同步写法的优点是逻辑简单，两个栈高度一致，不会出现状态错乱。但代价是辅助栈可能存了很多重复元素，浪费空间。比如压入 1、2、3、4，辅助栈里全是 1，其实只存一个 1 就够了。

所以就有了非同步写法：只有在 val 不大于辅助栈栈顶时，才把 val 压入辅助栈。pop 时，如果数据栈弹出的值恰好等于辅助栈栈顶，辅助栈才需要同时弹出。这里有一个关键细节，判断时必须用<=，而不是<。因为如果有多个相同的最小值，比如连续压入两个 2，辅助栈如果只在val < 栈顶时压入，那么弹出一个 2 后，辅助栈里就没有 2 了，getMin 会返回错误结果。

class MinStack { private Deque<Integer> data; private Deque<Integer> minStack; public MinStack() { data = new ArrayDeque<>(); minStack = new ArrayDeque<>(); } public void push(int val) { data.push(val); // 空栈直接压入，否则压入较小值 if (minStack.isEmpty() || val <= minStack.peek()) { minStack.push(val); } } public void pop() { int val = data.pop(); // 弹出的元素恰好是最小值之一，辅助栈同步弹出 if (val == minStack.peek()) { minStack.pop(); } } public int top() { return data.peek(); } public int getMin() { return minStack.peek(); } }

这里有一个 Java 容易踩的坑：如果用Integer做比较，==在小数值范围（-128 到 127）内没问题，超出这个范围就不可靠，必须用equals。刷题时我用int或者直接在 pop 里用val == minStack.peek()一般没事，因为 LeetCode 的测试用例整数范围不一定安全，写成minStack.peek().equals(val)更稳妥。

同步辅助栈和非同步辅助栈在时间上都是 O(1)，区别只在空间。我个人的习惯是面试时先写同步版本，因为思路好讲清楚，代码可读性高，不容易出 bug。如果面试官追问能不能优化空间，再改成非同步版本。

3. 字符串解码与每日温度：从“处理顺序”到“单调栈思维”

3.1 字符串解码：数字、括号、字母的三元状态处理

字符串解码这题是四道里最容易写烦的一道，因为要同时处理数字、左括号、右括号、字母四种字符，而且数字可能是多位数，括号可以多层嵌套。

题目示例3[a2[c]]的期望输出是accaccacc。从外层看，3[...]要把括号内内容重复三次；从内层看，2[c]先把 c 重复两次变成 cc，整个内层结果是acc，再被外层重复三次。这个“从内向外逐层构建”的过程，天然适合用栈把外层状态保存起来。

我在实现时选了两个栈：numStack存数字，strStack存内层结果构建前的字符串状态。另设一个StringBuilder cur作为当前层的构建容器，一个整型num用来累积连续的数字。

扫描字符时的逻辑是这样的：

• 数字字符，num = num * 10 + (c - '0')，这一步处理多位数，例如100[leetcode]中的 100。
• 左括号[，说明进入新一层，把当前的num和cur分别压栈，然后重置cur和num。压栈的cur临时保存了外层已经拼好的字符串。
• 右括号]，说明这一层结束，弹出数字k和外层字符串prev，把当前cur重复k次后接到prev末尾，结果作为新的cur。
• 普通字母，直接追加到cur。

代码实现如下。

import java.util.ArrayDeque; import java.util.Deque; class Solution { public String decodeString(String s) { Deque<Integer> numStack = new ArrayDeque<>(); Deque<StringBuilder> strStack = new ArrayDeque<>(); StringBuilder cur = new StringBuilder(); int num = 0; for (char c : s.toCharArray()) { if (Character.isDigit(c)) { num = num * 10 + (c - '0'); } else if (c == '[') { // 保存外层状态，进入新一层 numStack.push(num); strStack.push(cur); cur = new StringBuilder(); num = 0; } else if (c == ']') { // 内层结束，重复并拼接回外层 int k = numStack.pop(); StringBuilder prev = strStack.pop(); for (int i = 0; i < k; i++) { prev.append(cur); } cur = prev; } else { cur.append(c); } } return cur.toString(); } }

这里最容易出错的有三个地方。一是num在[之后必须重置为 0，否则会干扰下一轮数字解析。二是cur在压栈之后要 new 一个新对象，如果直接复用同一个引用，后面修改会污染已经保存的外层状态。三是 StringBuilder 的 append 顺序，prev.append(cur)是外层在前、内层在后，写反了就整个字符串顺序颠倒了。

这道题也能用递归做，遇到数字和[就递归解析子串，遇到]返回结果，本质上就是“用系统调用栈代替显式栈”。递归代码短一些，但面试时讲清楚栈深度与括号嵌套层数的关系反而要费点口舌，我一般优先写双栈版本。

3.2 每日温度：单调递减栈如何省掉双重循环

每日温度这题的朴素思路是双重循环，对每个位置向后扫描找到第一个温度更高的位置，时间复杂度 O(n^2)，数据量一大必然超时。单调栈的核心优化点是：让每个元素只入栈一次、出栈一次，总复杂度降到 O(n)。

先看题目数据，temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，输出要求是[1, 1, 4, 2, 1, 1, 0, 0]。我从左到右遍历，利用一个栈保存“暂时还没有找到更高温度的下标”。栈从底到顶保持递减关系，也就是栈顶对应的是当前未解决元素中温度最低的那一个。

遍历到第 i 天时，如果当前温度高于栈顶下标对应的温度，说明栈顶这天等到了它的“下一个更高温度”，可以确定答案了。此时弹出栈顶下标 idx，res[idx] = i - idx。这个 while 循环会一直执行，直到当前温度不再高于栈顶，或者栈为空，然后把 i 压栈。

这样一来，每个下标最多被弹出一次，总时间是 O(n)。代码量其实很短。

import java.util.ArrayDeque; import java.util.Deque; class Solution { public int[] dailyTemperatures(int[] temperatures) { int n = temperatures.length; int[] res = new int[n]; // 栈内存放下标，栈底到栈顶对应温度递减 Deque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i < n; i++) { // 当前温度比栈顶温度高时，栈顶找到了答案 while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) { int prev = stack.pop(); res[prev] = i - prev; } stack.push(i); } // 留在栈里的说明后面没有更高温度，默认值为 0 return res; } }

写这道题特别容易把 while 写成 if，一旦写成 if，栈内多个待处理元素就只处理栈顶那一个，后面的元素即使等到了更高温度也没机会出栈，答案自然不对。另一个容易忘的是栈内存的是下标而不是温度值，因为计算天数差必须用到下标差。

单调栈的模板还可以迁移到“下一个更大元素”系列、接雨水、柱状图中最大的矩形。可以说每日温度是理解单调栈最友好的一道题，因为它没有下标循环节那些乱七八糟的变形，完全贴合原生模板。我自己在面试中被问过“下一个更大元素”的变体，当时直接把每日温度的代码思路套上去，很快就完成了解答。

4. 四题横向对比与Java实现细节

4.1 复杂度、核心栈用法与易错点速查表

四道题放在一起横向看，更容易发现规律。我把复杂度、核心手法和易错点整理成了下面这张表，刷题的时候可以用它做自检。

从这张表能看出，栈题的空间复杂度几乎都是 O(n)，因为栈本身就是额外空间。真正拉开差距的点不在“用什么栈”，而在“什么时候入栈、什么时候出栈、栈里存什么”，这三问想清楚了，代码基本不会错。

4.2 Java里Deque与Stack的选择，以及刷题建议

Java 老代码里经常看到Stack，但它继承自Vector，所有方法默认加锁，存在不必要的性能开销。更重要的是它属于历史遗留集合类，现代 Java 官方文档也建议优先使用ArrayDeque来实现栈语义。我刷力扣默认写Deque<Integer> stack = new ArrayDeque<>()，这也是目前社区的主流写法。

ArrayDeque的几个常用方法要记牢：push压栈、pop弹栈、peek查看栈顶、isEmpty判空。有一点要注意，ArrayDeque不允许存放null值，如果你的数据本身可能为空，要提前处理，否则会抛空指针异常。

还有两个实用技巧。第一，LeetCode 同一道题，用ArrayDeque比用LinkedList快不少，因为数组结构连续内存、缓存友好。第二，如果追求极致性能，直接用数组模拟栈，比如int[] stack = new int[n]加一个top指针，在有效括号里我已经展示过这种写法。数组模拟栈没有任何方法调用开销，但我只在确定栈最大容量不会超过数组长度时才用它，否则可能越界。

刷题时我还建议先手动模拟一遍示例数据，再写代码。尤其是单调栈，第一次接触的人很容易搞混“栈内递减”和“栈内递增”的表述，虽然只是方向问题，但写错一个符号整个程序都错。我自己的习惯是：让栈顶始终是“当前待处理元素中离我最近的、最弱的那个”，这样 while 比较方向就不会错。

5. 四类题的常见问题与避坑指南

5.1 我踩过的几个坑

先说有效的括号。有一段时间我用Map.of(')', '(')做映射，但判断右括号用的是map.containsKey(c)，这个没问题。可是我见过不少人会在 map 里同时放左右括号，结果遇到左括号也走containsKey分支，弹栈逻辑全乱。最稳妥的思路是 map 只放右括号到左括号的映射，遇左括号统一入栈。

再说最小栈。非同步写法里的<=真的是个经典陷阱。我一个同事在面试时写成了<，被面试官追问了一个重复最小值用例之后才反应过来。原因前面说过：重复的最小值需要在辅助栈里保留多份，否则弹掉一份之后最小值就丢了。这个问题在代码 review 里也经常出现，所以我在本地把这个用例直接记录成测试用例，每次写完就跑一遍。

字符串解码的坑更多是状态管理。我最初写的时候，num在遇到[之后忘记重置，导致2[a]3[b]这种输入里的 3 被解析成 23，整个输出完全不对。后来我总结了一个检查方法：任何遇到[的分支，都必须同时考虑num清零和cur重置这两件事，漏了一个就说明状态机没写好。

每日温度的问题集中在 while 上。我遇到过很多次，明明想清楚了单调栈流程，一着急就写成 if，只弹出栈顶元素。调试的时候发现后面的元素答案全是 0，再回头改又得重跑一遍。我的经验是，只要“当前元素可能连续解决多个栈内元素”，就必须用 while，不能因为样例里恰好只有一次弹出就用 if 糊弄过去。

5.2 面试里的栈题考察点与延伸学习方向

栈题在面试中的考察重点不只是能不能 Accepted，更看重你能不能讲清楚“为什么用栈”。我面过一些候选人，代码写得很顺，但一被问“为什么这里要用栈”就愣住了。所以刷题阶段就要养成自问自答的习惯：这道题如果不让用栈，你会怎么做？你的解法在什么情况下空间会退化？

这四个题目的标准追问点我也整理一下。有效的括号会问“如果括号类型不止三种怎么办”，本质是 map 的可扩展性。最小栈会问“能不能再省空间”，对应非同步辅助栈的优化。字符串解码会问“递归和栈哪个更好”，可以借机解释系统调用栈和显式栈的取舍。每日温度会问“如果不是找更高温度，而是找更低温度怎么办”，只需要把比较符号反过来。

往后续的学习方向，我建议按这三个阶段推进：第一阶段把栈的基础操作和这四道题刷熟；第二阶段做“下一个更大元素”、逆波兰表达式求值、基本计算器这类栈的应用题；第三阶段挑战接雨水、最大矩形、柱状图中最大的矩形，这些题把单调栈和分治思想结合在一起，是栈题的天花板区域。栈这个专题刷下来，最大的收获不是记住某道题的解法，而是建立起“延迟处理”的意识。很多问题一眼看过去没有思路，但把“等一下再处理”这个念头转出来，解法往往自己就浮出来了。

我个人在实际操作中的体会是，栈题是所有数据结构题里性价比最高的。它不像树那样有大量递归模板，也不像图那样需要背邻接表、拓扑排序，只要掌握“最近相关性”的判断，再熟悉一点单调栈的变体，Hot100 这部分基本可以稳定拿下。如果你也在刷力扣，建议把这四题放在同一天完成，做完之后自己动手写一张速查表，效果会比零散刷题好很多。