力扣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 DequeCharacter stack new ArrayDeque(); MapCharacter, 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全局变量记录最小值是 1pop 掉 1 之后整个栈里剩下的最小值变成 2全局变量却不知道。解决办法是保存“每个状态时刻的最小值”而不是只保存当前一个值。最直观的做法是准备两个栈数据栈照常存元素辅助栈存对应状态下的最小值。push 时数据栈正常压入 val辅助栈压入 min(当前栈顶最小值, val)。pop 时两个栈一起出栈。这种同步写法的优点是逻辑简单两个栈高度一致不会出现状态错乱。但代价是辅助栈可能存了很多重复元素浪费空间。比如压入 1、2、3、4辅助栈里全是 1其实只存一个 1 就够了。所以就有了非同步写法只有在 val 不大于辅助栈栈顶时才把 val 压入辅助栈。pop 时如果数据栈弹出的值恰好等于辅助栈栈顶辅助栈才需要同时弹出。这里有一个关键细节判断时必须用而不是。因为如果有多个相同的最小值比如连续压入两个 2辅助栈如果只在val 栈顶时压入那么弹出一个 2 后辅助栈里就没有 2 了getMin 会返回错误结果。class MinStack { private DequeInteger data; private DequeInteger 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) { DequeInteger numStack new ArrayDeque(); DequeStringBuilder 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 天时如果当前温度高于栈顶下标对应的温度说明栈顶这天等到了它的“下一个更高温度”可以确定答案了。此时弹出栈顶下标 idxres[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]; // 栈内存放下标栈底到栈顶对应温度递减 DequeInteger 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)O(n)左括号入栈右括号配对弹出栈空时遇到右括号奇数长度没剪枝最小栈O(1)O(n)同步或非同步辅助栈重复最小值时判断要用 Integer 比较用 equals字符串解码O(n)O(n)双栈分别存数字和字符串多位数解析后忘记重置 numcur 没有 new 新对象每日温度O(n)O(n)单调递减栈存放下标while 写成 if栈内存下标不是温度从这张表能看出栈题的空间复杂度几乎都是 O(n)因为栈本身就是额外空间。真正拉开差距的点不在“用什么栈”而在“什么时候入栈、什么时候出栈、栈里存什么”这三问想清楚了代码基本不会错。4.2 Java里Deque与Stack的选择以及刷题建议Java 老代码里经常看到Stack但它继承自Vector所有方法默认加锁存在不必要的性能开销。更重要的是它属于历史遗留集合类现代 Java 官方文档也建议优先使用ArrayDeque来实现栈语义。我刷力扣默认写DequeInteger 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 这部分基本可以稳定拿下。如果你也在刷力扣建议把这四题放在同一天完成做完之后自己动手写一张速查表效果会比零散刷题好很多。