1. 为什么把四道栈题放到同一篇里复盘这是力扣Hot100系列的第15篇。这轮刷到栈主题的时候我本来想按题目难度一天一道地过结果发现这样效果很差——今天做有效的括号明天做每日温度两道题之间隔了十几个小时每次都要重新回忆一遍“栈里到底该存什么”。后来我换了个策略把Hot100里栈这一主题的四道核心题集中在一个晚上过一次做完顺手写了这篇总结效果比零散刷好得多。1.1 四道题对应栈的三种典型能力先明确一下Hot100涉及的栈题不止四道但这四道刚好覆盖了栈在算法题中最常出场的三个用途符号配对、辅助状态存储、单调性维护。有效的括号LeetCode 20对应的是配对场景利用的是栈“最近匹配”的特性左括号顺序入栈遇到右括号时栈顶恰好就是最近的未匹配左括号。最小栈LeetCode 155对应辅助状态存储考察的是在常规栈操作之外如何额外维护一个最小值而且要求 getMin 是 O(1)。字符串解码LeetCode 394对应嵌套结构处理方括号套方括号的情况下“先遇到的要等内层处理完才能继续”这跟栈的后进先出正好吻合。每日温度LeetCode 739对应单调性维护是单调栈的入门模板题核心是让每个元素只入栈一次、出栈一次把暴力解法的 O(n^2) 压到 O(n)。把四道题放在一起看你会发现它们没有一题是真的在考“栈的API怎么写”考的全都是一件事在具体场景里什么时机入栈、什么时机出栈、出栈的时候做什么。1.2 刷题顺序与前置知识如果你是想照着我这条路集中刷我建议按这个顺序来有效的括号、最小栈、字符串解码、每日温度。前两题训练的是栈的基础直觉和辅助结构设计后两题开始涉及嵌套和单调性难度是逐步叠加的直接上来就做每日温度容易一头雾水。前置知识只需要准备两件事。第一Java 里用 Deque 接口和 ArrayDeque 实现类会 push、pop、peek 三个方法就够了第二要对时间复杂度的常见量级有概念至少能分清楚 O(n^2) 和 O(n) 的差距有多大。至于 Stack 类为什么在算法题里不该用我后面天然会提到一次先别急。2. 有效的括号配对类栈题的标准模板2.1 核心逻辑用HashMap预处理配对关系先说题目本身给定一个只包含()[]{}三种括号的字符串判断括号是否有效。有效的定义有两个一是每个左括号必须有同类型的右括号闭合二是闭合顺序必须正确。像([)]这种虽然每种括号都出现了但顺序是交叉的就不算有效。大多数人的第一反应是写一个 switch 或者一堆 if-else 处理三种括号的匹配这个思路没错但写出来的代码普遍很啰嗦。我自己的做法是先用一个 HashMap 把配对关系存下来方向是“右括号映射左括号”然后用一个containsKey判断当前字符是哪一类。class Solution { public boolean isValid(String s) { MapCharacter, Character map new HashMap(); map.put(), (); map.put(], [); map.put(}, {); DequeCharacter stack new ArrayDeque(); for (char c : s.toCharArray()) { if (!map.containsKey(c)) { // 左括号直接入栈 stack.push(c); } else { // 右括号需要栈顶有对应的左括号 if (stack.isEmpty() || stack.pop() ! map.get(c)) { return false; } } } return stack.isEmpty(); } }这里的设计关键在映射方向。如果存的是“左括号映射右括号”那么处理每个字符前还得先判断它到底是左还是右代码里就得多一个分支反过来存右括号映射左括号一个containsKey就把左右括号天然分开不包含的说明是左括号包含的说明是右括号。这个小技巧不仅让代码干净面试的时候也能体现出你处理状态分类的思路。2.2 边界条件与代码细节配对题的坑基本都在边界条件上。我第一遍写的时候漏了两种情况这里直接列出来你们避着走。栈空时来了右括号比如]第一个字符就是右括号此时栈里什么都没有直接pop()会报错。好一点的写法是像上面那样先判断stack.isEmpty()再决定是否匹配栈空就立刻返回 false。全部处理完栈还有剩余比如(()左括号数量多于右括号循环结束后栈里还剩一个(这时候必须返回stack.isEmpty()的布尔值而不是默认返回 true。提示:Java 里刷题用 Stack 还是 ArrayDeque我建议一律用 ArrayDeque。Stack 继承自 Vector所有方法都带 synchronized单线程场景下这些同步完全是负担ArrayDeque 的 push/pop/peek 行为跟 Stack 一致性能更好也没有过时方法的问题。另外一个很小的优化如果字符串长度是奇数直接返回 false。括号一定是成对出现的奇数长度必然无效。这个判断放在循环之前虽然对性能的影响微乎其微但面试的时候主动提一句面试官会觉得你想问题够全面。2.3 复杂度与扩展有效的括号时间复杂度是 O(n)因为每个字符只入栈或出栈一次空间复杂度是 O(n)栈最坏情况下要存 n/2 个左括号。这个模板的适用范围比想象中广。后续你要是遇到类似“检查HTML标签是否规范闭合”“判断一段简化JSON的括号结构”这样的场景核心逻辑完全一样只是配对表的内容不同。它算是所有配对类问题的地基后面做字符串解码的时候你会发现两者在思想上是一脉相承的——都用栈来处理“先遇到后处理”的关系。3. 最小栈辅助栈设计思路的第一次考验3.1 暴力法的失败与空间换时间的必然最小栈是一道设计题要求实现一个支持push、pop、top、getMin的栈其中getMin必须在 O(1) 时间内返回当前栈的最小值。很多人看到“返回最小值”的第一反应是维护一个全局变量 min每次 push 的时候更新它。这个想法在 push 阶段是成立的问题出在 pop如果你把当前的最小值元素弹出去了那新的最小值是谁你只能把剩下的元素重新遍历一遍才能知道getMin 就退化成 O(n) 了。这道题的核心矛盾就是最小值是动态变化的你不能只记住一个快照你得记住每一个历史状态。而栈这种结构恰恰能帮我们记录历史状态——你只需要再开一个栈同步记录“当前栈内元素的最小值序列”问题就解决了。这本质上就是空间换时间而且是这个场景下最自然、最不容易出错的解法。3.2 辅助栈方案同步存最小值辅助栈方案的思路很直接主栈正常存数据辅助栈的栈顶任何时候都保存当前主栈中的最小值。关键操作在 push 阶段辅助栈为空时直接 push val辅助栈非空时push min(val, 辅助栈栈顶)。这样设计之后辅助栈其实存的是“每个版本的最小值快照”。主栈里每多一个元素辅助栈里就多一个对应的最小值两栈的长度永远一致。pop 的时候两个栈同步弹出不需要任何额外判断写起来非常省心。class MinStack { private DequeInteger stack; private DequeInteger minStack; public MinStack() { stack new ArrayDeque(); minStack new ArrayDeque(); } public void push(int val) { stack.push(val); if (minStack.isEmpty()) { minStack.push(val); } else { minStack.push(Math.min(val, minStack.peek())); } } public void pop() { stack.pop(); minStack.pop(); } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); } }这里最重要的思维转变是辅助栈不是“存所有出现过的历史最小值”而是“存主栈每个长度下的当前最小值”。这两个说法看起来差不多但实现起来差别很大。前者可能要考虑“某个旧的最小值是否已经被弹出”这类问题后者完全不需要因为两个栈是同步的。3.3 差值栈方案与溢出陷阱如果面试官追问“能不能不用辅助栈”你需要知道有一种基于差值的写法。它的思路是栈里不存原始值只存“当前值和当前最小值的差值”。具体流程是维护一个全局变量 minpush x 时计算 diff x - min将 diff 入栈。如果 diff 小于 0说明 x 比当前最小值还小需要把 min 更新为 x如果 diff 大于等于 0min 保持不变。pop 的时候反过来栈顶 diff 如果是负数说明被弹出的是当前最小值弹出后需要用min - diff找回上一阶段的最小值如果 diff 是正数min 不变top 的值用min diff还原。class MinStack { private DequeLong diffStack; private long min; public MinStack() { diffStack new ArrayDeque(); } public void push(int val) { if (diffStack.isEmpty()) { min val; diffStack.push(0L); return; } long diff (long) val - min; diffStack.push(diff); if (diff 0) { min val; } } public void pop() { long diff diffStack.pop(); if (diff 0) { min min - diff; } } public int top() { long diff diffStack.peek(); if (diff 0) { return (int) min; } return (int) (min diff); } }代码里必须用 long 存差值这一点容易被人忽略。题目给的 val 范围是 int但假设当前 min 是 -2147483648push 进来一个 2147483647两者的差值就是 4294967295已经超出 int 范围。用 long 就是为了避免这种极端情况下的溢出。3.4 面试建议选哪个方案我的建议是面试现场首选辅助栈方案。它逻辑直观、实现简单、解释起来非常顺畅差值栈更适合私底下研究当作思维训练但不适合作为现场的主答方案。面试的时候说一句“我知道差值栈可以省空间但在可读性和正确性上辅助栈更稳妥”这句话本身就足够展现你的技术判断力了。毕竟在真实工程里能维护的正确代码永远优于炫技但脆弱的代码。4. 字符串解码嵌套场景下的栈状态管理4.1 双栈解法的状态机拆解字符串解码的题目要求是把3[a2[c]]这种带数字和方括号的字符串解码成accaccacc规则是k[encoded_string]中括号里的内容重复 k 次而且方括号可以嵌套。为什么这道题天然适合用栈就是因为嵌套结构。最内层的括号必须先展开展开的结果还要被外层继续使用这种“先遇到的最后处理、后遇到的先处理”的顺序就是后进先出。更直白地说括号的闭合顺序决定了处理顺序而栈天然维护的就是这个闭合顺序。解法上我推荐双栈方案一个数字栈存重复次数一个字符串栈存当前状态。遍历字符串的每一步其实是一个小小的状态机遇到数字累加成一个完整整数注意多位数字遇到左括号把当前已构建的字符串压入字符串栈然后重置当前字符串遇到右括号弹出数字栈的重复次数和字符串栈的前缀把当前字符串重复后拼接回去遇到普通字符直接追加到当前字符串。class Solution { public String decodeString(String s) { DequeInteger countStack 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 [) { countStack.push(num); strStack.push(cur); cur new StringBuilder(); num 0; } else if (c ]) { int repeat countStack.pop(); StringBuilder prev strStack.pop(); for (int i 0; i repeat; i) { prev.append(cur); } cur prev; } else { cur.append(c); } } return cur.toString(); } }这个解法的核心操作集中在右括号分支把当前字符串重复 repeat 次之后不是返回结果而是拼接到之前保存的前缀后面然后让 prev 成为新的 cur。这一步做完当前状态就恢复到了处理这层括号之前的样子外面的内容可以继续往上加。如果漏了strStack.pop()多层嵌套立刻处理不了。4.2 递归方案与全局下标陷阱这道题也可以用递归解代码看起来比双栈更简洁因为函数调用栈替我们处理了嵌套。但递归版有个隐蔽的坑必须用一个成员变量 index 记录扫描位置递归返回时才知道外层字符串应该从哪里继续。class Solution { private int index 0; public String decodeString(String s) { StringBuilder sb new StringBuilder(); while (index s.length()) { char c s.charAt(index); if (Character.isDigit(c)) { int num 0; while (index s.length() Character.isDigit(s.charAt(index))) { num num * 10 (s.charAt(index) - 0); index; } index; // 跳过[ String inner decodeString(s); index; // 跳过] for (int i 0; i num; i) { sb.append(inner); } } else if (c ]) { return sb.toString(); } else { sb.append(c); index; } } return sb.toString(); } }递归版最需要注意的是遇到右括号时必须return把这个字符串结果返回给上一层。如果这里不 return 而只是 index内层递归返回后外层会继续把右括号当作普通字符处理结果完全乱掉。我在这个地方卡了很久后来想通了——右括号是这层递归的终止信号它提醒我们这一层的括号内容已经解析完了。4.3 拼接顺序与高频翻车点我再提醒一个新手极易翻车的地方拼接顺序。回到3[a2[c]]这个例子当内层第一个右括号出现时cur 是ccprev 是a重复次数是 2执行prev.append(cur)之后 prev 变成acc。然后第二个右括号出现cur 是accprev 是空字符串重复次数是 3拼完得到accaccacc。注意这里必须写成prev.append(cur)而不是cur.append(prev)。前者是“在之前状态的基础上后面追加当前重复结果”后者会把前缀放到重复结果的后面顺序完全颠倒。我当时就是因为在这个细节上没想清楚得到aacc而不是accdebug 了好一会儿才意识到是拼接方向反了。提示:调试这类嵌套题时别用眼睛看。我推荐在右括号分支打一个临时输出打印 cur、prev、repeat 三个值肉眼推演一遍之后你会对入栈出栈的时机理解得特别清楚。5. 每日温度单调栈的实战推演5.1 暴力法的问题与单调栈的思路每日温度的题目描述很朴实给定一个温度数组 temperatures返回一个等长数组每个位置的值表示“要等多少天才能等到一个更高的温度”如果后面没有更高温度填 0。比如[73,74,75,71,69,72,76,73]对应的答案就是[1,1,4,2,1,1,0,0]。暴力法就是两层循环对每个位置 i 往后扫找到第一个大于它的值就算出距离。这个方法的问题在于重复计算太严重了扫描 i 的时候已经路过了一堆比它大的值这些信息没有被保存轮到 i1 的时候还得重新扫一遍。当数组长度到 10^5 量级O(n^2) 直接超时。单调栈的思路是换个角度思考与其让每个元素主动去右边找答案不如让答案自己送上门来。我们维护一个从栈底到栈顶温度递减的栈同时栈里存的是下标而不是温度值。遍历数组时如果当前温度比栈顶下标对应的温度高说明栈顶那一天的答案已经确定了——就是当前下标减去栈顶下标。不断弹出直到栈顶温度不再小于当前温度然后把当前下标入栈。为什么存下标而不是存温度值因为答案要求的是天数差只有下标能计算出“隔了多少天”。5.2 完整推演递减栈的入栈出栈过程下面我逐行推演一遍[73,74,75,71,69,72,76,73]这个例子你跟着走一遍就全通了。i0栈空0 入栈。栈[0]i1温度 74 大于栈顶下标 0 的温度 73弹出 0answer[0] 1 - 0 1然后 1 入栈。栈[1]i2温度 75 大于 74弹出 1answer[1] 12 入栈。栈[2]i3温度 71 小于 753 入栈。栈[2,3]i4温度 69 小于 714 入栈。栈[2,3,4]i5温度 72 大于 69弹出 4answer[4] 172 还大于 71弹出 3answer[3] 5 - 3 272 小于 75停止弹出5 入栈。栈[2,5]i6温度 76 大于 72弹出 5answer[5] 176 大于 75弹出 2answer[2] 6 - 2 46 入栈。栈[6]i7温度 73 小于 767 入栈。栈[6,7]循环结束栈里剩下的下标 6 和 7 在右边都没有更高温度answer 保持初始值 0。最终答案[1,1,4,2,1,1,0,0]和题目样例完全一致。关键要体会的位置是 i3 和 i4 这两个连续递减的天。它们入栈之后一直压在栈里直到 i5 出现才一个接一个被弹出。这说明栈里的元素是“悬而未决”的状态——它们都在等一个比自己大的值而更大的值一旦出现会一次性解决掉栈里所有能解决的元素。class Solution { public int[] dailyTemperatures(int[] temperatures) { int n temperatures.length; int[] answer new int[n]; DequeInteger stack new ArrayDeque(); for (int i 0; i n; i) { while (!stack.isEmpty() temperatures[i] temperatures[stack.peek()]) { int idx stack.pop(); answer[idx] i - idx; } stack.push(i); } return answer; } }5.3 单调栈套路总结与变体延伸刷完这道题之后我把单调栈的思考套路总结成了三句话后面遇到同类题直接套栈里存下标方便后续计算距离或面积新元素与栈顶比较破坏单调性时弹出同时记录答案循环结束之后栈里剩余的元素答案保持默认值。用这个套路可以延伸出一大串题目下一个更大元素 I/IILeetCode 496/503、接雨水LeetCode 42、柱状图中最大的矩形LeetCode 84。区别只在于比较方向、答案记录方式、以及出栈时计算的是距离差还是面积。我以前的做法是刷完每日温度立刻做一道“下一个更大元素”那道题几乎可以复制粘贴思路再做接雨水就会看到单调栈在出栈时还需要额外维护一个宽度。形成这种“锚点题连刷一片”的习惯之后我看到一个题目描述里出现“找最近的更大值/更小值”这类字眼第一反应就是单调栈根本不用纠结用什么数据结构。6. 刷完后我沉淀下来的三个判断标准6.1 第一先问“栈里存什么”再问“何时出栈”以前我做栈题上来就写代码写着写着才发现栈里的元素类型选错了。现在我把顺序反过来先想清楚栈里存的是值还是下标是字符还是字符串然后再想入栈和出栈的条件是什么。这四个题就是四种不同的答案。有效的括号栈里存左括号字符最小栈的辅助栈存的是历史最小值字符串解码的两个栈一个存数字一个存前缀字符串每日温度的栈里存的是下标。每次动手前先回答这个问题代码基本不会写跑偏。6.2 第二空间换时间不是坏事但要能说明理由最小栈和字符串解码这两个题都涉及额外空间的滥用风险。有些解法写出来确实能过但空间复杂度是别人的两倍还不止。我在刷题的时候养成了一个习惯每写完一个解法主动问自己能不能把额外空间省掉以及省掉之后代码是否还一样清晰可维护。最小栈的辅助栈和差值栈就是典型的对比。辅助栈多 O(n) 空间但简单可靠差值栈省空间但边界条件多、容易出错。在真实工程里这种“多一块空间换清晰度”的取舍太常见了面试的时候主动把这个权衡说出来比单纯背解法加分得多。6.3 第三把同类型题目连在一起刷效率远高于随机刷题这轮把四道栈题集中复盘之后我最大的感触是知识点的记忆是有索引的。零散刷题等于每次都要重建索引而集中刷同类题时前面的题会成为后面题的背景知识。比如没有做有效的括号字符串解码里“为什么右括号触发处理”就容易想不通没有做每日温度后面接雨水的“宽度累积”就更难理解。我个人目前的刷题节奏是每个周末抽一个晚上集中过 Hot100 里同一个数据结构的四到六道题之后花半小时写一篇总结把每道题的核心套路压缩成一两句话记下来。过一段时间再翻回来就算细节忘了看到“递减栈”“辅助栈同步快照”“右括号触发展开”这些关键词整个思路也能立刻恢复。这套方法对栈有效对二叉树、动态规划同样适用推荐你试试。