1. 内容整体设计与思路拆解栈Stack在力扣Hot100里看起来题目不多但每一道都踩在核心考点上。这次要聊的是四道题有效的括号、最小栈、字符串解码、每日温度。把这四道放一起做总结不是因为它们都用了栈这个数据结构而是因为它们分别代表了栈的四种典型用法——符号匹配、辅助栈、栈与递归的结合、单调栈。把这四种模式吃透栈相关的题目基本就拿下了一大半。先说说为什么是这四道题。有效的括号是最经典的栈入门题考察的是栈的后进先出特性在符号配对中的应用最小栈考察的是如何用空间换时间用一个辅助栈记录历史状态字符串解码是栈与递归的深度结合处理嵌套结构时栈的优势体现得淋漓尽致每日温度则是单调栈的典型应用把时间复杂度从暴力解的O(n²)降到了O(n)。这四道题目从易到难从基础到进阶刚好串起了一条完整的栈学习路径。我刷题的习惯是先自己做一遍再看题解最后写总结。这四道题里有效的括号和每日温度算是容易上手的最小栈和字符串解码则需要多想几步。尤其是字符串解码第一次遇到的时候大概率会卡住因为它不只是简单的入栈出栈还涉及到字符串拼接的顺序问题。先说我个人的学习建议如果你是刚开始刷力扣栈相关的题目不要急着用Java里的Stack类建议直接用ArrayDeque。后面我会专门解释为什么这里先卖个关子。2. 有效的括号符号匹配的经典考场2.1 题目分析与考点拆解有效的括号这道题题面很简单给定一个只包含( ) { } [ ]的字符串判断括号是否有效。有效需要满足两个条件左括号必须用相同类型的右括号闭合左括号必须以正确的顺序闭合。这道题放在Hot100里不是因为难而是因为它太基础了基础到几乎所有面试都会问。它的考点其实有三个层次第一个层次是能不能想到用栈。遇到左括号就压栈遇到右括号就弹栈比对这是最直观的思路。第二个层次是代码的简洁性能不能用Map把配对的逻辑写得干净利落。第三个层次是边界条件的处理比如空字符串算不算有效遍历结束后栈是不是空的。很多人写这道题的时候会把左右括号分别处理用一堆if-else判断。代码能跑通但不够优雅。我推荐的做法是用HashMap先把配对关系存下来然后用Deque模拟栈操作。这样代码量少逻辑也清晰。2.2 Java实现与踩坑记录class Solution { public boolean isValid(String s) { // 边界条件奇数长度直接返回false if (s.length() % 2 1) { return false; } MapCharacter, Character pairs new HashMap() {{ put(), (); put(], [); put(}, {); }}; DequeCharacter stack new ArrayDeque(); for (int i 0; i s.length(); i) { char ch s.charAt(i); if (pairs.containsKey(ch)) { // 栈为空或者栈顶不匹配直接返回false if (stack.isEmpty() || !stack.peek().equals(pairs.get(ch))) { return false; } stack.pop(); } else { stack.push(ch); } } return stack.isEmpty(); } }这里有几个细节值得展开说。第一个细节为什么先判断长度是否为奇数因为有效的括号字符串长度一定是偶数这个剪枝能让代码提前返回省去不必要的遍历。虽然这个优化对性能影响不大但体现的是思考的严谨性。第二个细节为什么用peek()而不是pop()因为先看一眼栈顶是不是匹配的左括号不匹配的话直接返回false匹配的话再弹出去。这样就把“比对”和“弹出”两个步骤分开了逻辑更清晰。第三个细节遍历结束后为什么要检查stack.isEmpty()因为可能存在这种情况字符串是((()全是左括号没有右括号这时候遍历完了栈里还有元素说明括号没有闭合是无效的。我实际刷题时踩过一个坑一开始我用的是Java的Stack类代码能过但后来看了官方题解发现推荐用ArrayDeque。查了一下原因Stack继承自Vector所有方法都加了synchronized锁在多线程环境下是线程安全的但单线程下白白增加了开销。而且Stack这个类本身设计得比较老旧官方文档都建议优先使用Deque接口的实现类。提示力扣刷题时栈的操作一律用ArrayDeque。push()对应addFirst()pop()对应removeFirst()peek()对应peekFirst()。不过ArrayDeque本身就有push、pop、peek方法直接用就行。但要注意ArrayDeque不允许存储null元素而Stack允许这一点在少数场景下会有影响。3. 最小栈辅助栈的空间换时间3.1 设计思路与两种方案对比最小栈这道题的题面是设计一个支持push、pop、top、getMin操作的栈结构要求getMin的时间复杂度是O(1)。如果只用一个栈getMin操作要么遍历整个栈找最小值时间复杂度O(n)要么就得想办法在入栈时就记录最小值。最直观的方案是用辅助栈主栈正常存数据辅助栈同步存当前栈内的最小值。每次push的时候比较新元素和辅助栈栈顶的大小把较小的那个压入辅助栈。这样辅助栈的栈顶始终是当前栈内的最小值getMin直接返回辅助栈栈顶即可。具体来说push操作分两步主栈正常入栈辅助栈判断新元素是否小于等于栈顶如果是则压入新元素否则重复压入一个栈顶元素。这样两个栈的高度保持一致pop的时候两个栈一起弹同步性好代码也容易理解。其实还有一种方案只用一个栈栈里存的是当前元素与最小值的差值。这个方案省空间但实现起来比较绕需要额外的数学推导面试时容易出错。作为面试官我更愿意看到候选人能先把辅助栈方案讲清楚再提一下差值方案的思路就已经加分了。3.2 Java实现与边界讨论class MinStack { private DequeInteger stack; private DequeInteger minStack; public MinStack() { stack new ArrayDeque(); minStack new ArrayDeque(); // 初始化一个最大值占位避免peek空栈 minStack.push(Integer.MAX_VALUE); } public void push(int val) { stack.push(val); 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(); } }这里有一个很重要的初始化细节我在构造方法里先往minStack压了一个Integer.MAX_VALUE。这样做的目的是为了避免第一次push时minStack.peek()是空栈导致异常同时也让逻辑变得统一——每次push时不需要判断辅助栈是否为空。这个方案的空间复杂度是O(n)因为需要额外的栈来存最小值。在实际面试中如果面试官问能不能优化空间你可以提差值栈的思路但写代码的时候建议还是用辅助栈因为不容易出错。说一下我对辅助栈这个模式的理解它的本质是“用空间换时间”和动态规划的记忆化搜索思路相似。当我们需要频繁获取某个统计信息最小值、最大值但又不希望每次计算时就用一个额外的数据结构把这些信息维护起来。这种思路在算法题里非常常见最小栈只是个引子后面你会看到很多题目都用了类似的“辅助记录”技巧。注意ArrayDeque的push方法在栈为空时会自动扩容不用担心容量问题。但如果用LinkedList模拟栈要注意push和addFirst的语义差异实际效果是一样的只是可读性略有不同。4. 字符串解码栈与递归的深度结合4.1 题目拆解与难点定位字符串解码这道题的题面是给定一个经过编码的字符串返回解码后的字符串。编码规则是k[encoded_string]表示方括号内部的字符串正好重复k次。比如s 3[a2[c]]解码后是accaccacc。这里有两层嵌套先算内层2[c]得cc再算外层3[acc]得accaccacc。这道题是栈系列里比较有分量的一道难点在于嵌套结构。处理嵌套结构常见的思路有两种递归和栈。这两种思路本质上是一样的——递归的调用栈其实就是隐式的栈而Stack操作则是在模拟递归的过程。我推荐的写法是用栈模拟因为面试时用栈写更直观不容易被递归深度问题困扰。具体思路是这样的维护两个栈一个存数字重复次数一个存字符串当前层的结果。遍历字符串的每个字符分四种情况处理当前字符是数字时累加数字因为数字可能是多位数比如12[a]就得先读完12再处理后面的[。当前字符是字母时累加到当前字符串的末尾。当前字符是[时把当前的数字和字符串分别压入两个栈然后重置数字为0、字符串为空开始处理方括号内的新层级。当前字符是]时弹出数字栈顶拿到重复次数弹出字符串栈顶拿到之前已经拼接好的部分然后把当前字符串重复拼接在之前部分的后面。4.2 Java实现与执行流程演示class Solution { public String decodeString(String s) { DequeInteger countStack new ArrayDeque(); DequeStringBuilder strStack new ArrayDeque(); StringBuilder cur new StringBuilder(); int k 0; for (char ch : s.toCharArray()) { if (Character.isDigit(ch)) { k k * 10 (ch - 0); } else if (ch [) { countStack.push(k); strStack.push(cur); cur new StringBuilder(); k 0; } else if (ch ]) { int repeatTimes countStack.pop(); StringBuilder prev strStack.pop(); for (int i 0; i repeatTimes; i) { prev.append(cur); } cur prev; } else { cur.append(ch); } } return cur.toString(); } }我第一次写这道题的时候在cur new StringBuilder()这个地方纠结了很久。为什么遇到[要重新new一个StringBuilder因为每次遇到[就代表进入了一个新的嵌套层内层的字符串需要独立维护等到遇到]的时候再把内层的结果和之前的外层拼接起来。举个例子处理3[a2[c]]的时候过程是这样的遇到3k3遇到[countStack压入3strStack压入空的cur然后cur重置为新的空字符串遇到acur变成a遇到2k2遇到[countStack压入2strStack压入当前cura然后cur重置遇到ccur变成c遇到]弹出2和a把c重复2次拼接到a后面得到acccur变成acc遇到最后的]弹出3和空字符串把acc重复3次得到accaccacc这个过程中两个栈的高度始终一致一个存每一层的重复次数一个存每一层已拼接好的字符串。等到]弹出时当前层的cur负责的是方括号内的结果而strStack栈顶是方括号之前已经拼好的内容两者拼接起来就完成了这一层的解码。4.3 递归写法的对比与体会这道题也可以用递归做思路是遇到数字就递归处理后面的方括号部分。但使用递归要格外小心每个字符只能被处理一次否则时间复杂度会爆炸。我在评论区看到一些人写递归版本的时候因为索引移动的位置不对同一个方括号被解析了两次结果性能差得出奇。我个人的建议是栈版本的代码虽然看起来比递归稍微长一点但更好控制不容易出错。而且面试时大多数面试官更希望看到栈版本因为这能体现对数据结构的理解和掌控力。再补充一个性能方面的细节字符串拼接不要用String的操作尤其是重复拼接的循环里每次都会创建一个新的String对象时间复杂度会退化成O(n²)。用StringBuilder或StringBuffer能显著提升性能。这道题里整个流程都在做字符串拼接用StringBuilder几乎是必然的选择。5. 每日温度单调栈的实战应用5.1 暴力解法与单调栈的对比每日温度这道题的题面是给定一个数组temperatures对于每一天返回要等多少天才能等到一个更高的温度。如果之后都没有更高的温度返回0。暴力解法很好想两层循环外层遍历每一天内层往后找第一个比当前温度高的日子计算间隔天数。这个方法的时间复杂度是O(n²)在力扣的数据规模下会超时。单调栈的思路就要巧妙得多。我们维护一个栈栈里存的是下标这些下标对应的温度是递减的从栈底到栈顶温度依次降低。遍历每一天的温度时如果当前温度比栈顶下标对应的温度高说明栈顶那一天的“下一个更高温度”找到了就可以出栈并计算间隔天数。然后继续比较新的栈顶直到当前温度不大于栈顶温度然后把当前下标压入栈中。这样每个元素最多入栈一次、出栈一次时间复杂度是O(n)。5.2 Java实现与细节说明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) { int temp temperatures[i]; while (!stack.isEmpty() temp temperatures[stack.peek()]) { int prevIndex stack.pop(); answer[prevIndex] i - prevIndex; } stack.push(i); } return answer; } }这段代码不长但每个细节都值得琢磨。为什么从前往后遍历因为我们找的是“下一个更高温度”天然就是往后找。用栈记录“还没找到更高温度的那些天”当遇到更高温度时栈里的那些天的答案一次性结算。为什么栈内温度是递减的因为只要有新温度比栈顶高栈顶就会立刻出栈所以栈里留下的温度必然是递减序列。这个“递减栈”是单调栈的一种形式专门用来解决“下一个更大元素”这类问题。为什么用下标存而不是直接存温度因为最终要返回的是间隔天数只有知道下标才能算天数差。存温度的话算出间隔还需要额外查找对应的天数多此一举。这道题还有一个逆向遍历的写法从后往前遍历栈里维护的是“从当前位置往右看第一个更高温度的下标”。正向写法用while循环不断弹出处理逆向写法用if判断维护单调性。两种写法都能AC但正向写法的入栈次数更少处理逻辑更流畅。5.3 单调栈的适用场景总结做完了每日温度可以顺势总结一下单调栈的适用场景。如果你遇到的题目是“数组里每个元素的下一个更大元素/上一个更小元素/区间极值”这类问题优先考虑单调栈。单调栈的模板也很固定遍历数组当当前元素和栈顶元素不满足某种单调关系时弹出栈顶并结算答案然后把当前元素入栈。我刷了这么多题发现单调栈这个技巧在Hot100里出现频率不低但很多题不会直接告诉你用单调栈。比如柱状图中最大的矩形、接雨水、滑动窗口最大值这些题都能用单调栈解决。建议在掌握了每日温度的基础上把这几道题一并刷了效果会更好。注意单调栈有两种维护方式——递增栈和递减栈。每日温度用的是递减栈从栈底到栈顶温度递减因为我们要找的是“下一个更高温度”。如果题目变成“下一个更矮的温度”就要反过来用递增栈。判断用哪种栈核心看我们需要弹出的条件是什么。6. 常见问题与排查技巧实录这道四道题刷下来我踩过不少坑也整理了评论区大家经常问的问题挑几个典型的一起说说。6.1 数组/集合为空的判断时机刷有效的括号时最容易出错的点在“栈为空时遇到右括号”的情况。比如字符串是]只有单个右括号。正确逻辑是遇到右括号时先判断栈是否为空如果为空说明前面没有对应的左括号直接返回false。有些同学会把栈是否为空放在取栈顶之后判断也就是先stack.peek()再stack.isEmpty()这里顺序反了就会报错。写成!stack.isEmpty() stack.peek().equals(...)就把两个条件合在一起了既安全又简洁。6.2 用ArrayDeque还是Stack这个问题在评论区是老生常谈了。Java的Stack类是JDK 1.0就有的老类继承自Vector方法上都加了同步锁。在算法题这种单线程场景下加锁完全没有必要反而会拖慢性能。ArrayDeque作为Deque接口的实现类底层用循环数组实现操作效率高。它的push在头部插入pop在头部删除完全可以用作栈。在算法题中统一使用ArrayDeque是一个好习惯。唯一的坑是ArrayDeque的removeFirst()在栈为空时会抛异常而Stack的pop()为空时会抛EmptyStackException。两者的表现都是抛异常只是类型不同实际刷题时要注意异常类型的区别避免调试时找错方向。6.3 字符串解码的数字累加处理k[encoded_string]时数字可能是多位数比如12[a]或者100[leetcode]。有些人会写成k ch - 0这样遇到多位数时就出问题了因为后面一位数字会覆盖前面一位。正确的写法应该是k k * 10 (ch - 0)。这和把字符串转成整数的思路一样本质上就是在逐位还原数字。因为遍历字符串是一步一步来的遇到一个数字字符就先乘10再加当前位自然就把多位数拼出来了。6.4 每日温度的边界情况每日温度里如果最后几天温度一直下降它们对应的答案就是0。比如[30, 40, 50, 20, 10]最后两天20、10后面没有更高温度答案都是0。这正好是整个循环结束后栈里残留的下标它们的答案保持初始值0即可不需要额外处理。还有一个常见问题是为什么用int[temperatures.length]初始化答案数组因为Java数组默认初始化为0刚好符合题目对“找不到更高温度返回0”的要求不用手动再赋值一遍。6.5 算法的正确性验证每次写完代码除了提交AC之外建议自己再走一遍几个特殊的测试用例。有效的括号可以测空字符串、([)]嵌套错误、{[]}嵌套正确最小栈可以测连续push、pop之后getMin的值是否更新正确字符串解码可以测3[a]2[bc]这种相邻多个表达式的拼接每日温度可以测全递增、全递减、长度1的数组。多测边界用例才能真正理解算法为什么是对的也能在面试时熟练应对面试官的追问。7. 栈专题的横向串联与扩展思路把上面四道题放在一起回头看栈的运用场景其实可以归纳成一张清晰的脉络图。第一层是“栈的基本特性”后进先出。有效的括号直接利用了这一点左括号依次入栈遇到右括号时最近的左括号必然在栈顶出栈比对就行。这一层的关键是“配对”和“嵌套顺序”息息相关而栈天然能表达这种顺序。第二层是“用栈记录历史状态”最小栈用辅助栈记录每个时刻的最小值。这里的关键不是栈本身存了什么而是如何利用另一个栈同步记录“附加信息”让查询操作从O(n)降到O(1)。第三层是“栈模拟递归”字符串解码中的嵌套结构既可以递归处理也可以显式用栈模拟。这一层的关键在于理解递归调用的本质就是“栈帧的压入和弹出”把隐式栈改成显式栈一方面能避免递归深度限制另一方面也让代码更容易调试。第四层是“单调栈”每日温度把“下一个更高温度”的问题转化为“维护一个递减序列”。这一层的关键是理解单调栈的弹栈条件就是“答案可以结算”的条件。弹栈时计算的不再是配对关系而是元素之间的大小关系和位置关系。顺着这条脉络有一批题目可以一并攻克柱状图中最大的矩形对于每根柱子用单调栈找到左边和右边第一个比它矮的柱子乘以宽度就是面积。和每日温度的差别在于这里需要从两个方向找边界。接雨水与柱状图最大矩形类似用单调栈按行填充水位核心是“能积水的位置”取决于左右两侧较高的柱子。滑动窗口最大值用双端队列维护窗口内的候选最大值这其实是单调栈的思想在“滑动窗口”场景下的变形。用栈实现队列两个栈配合一个负责入队一个负责出队反复倒腾栈内元素来模拟队列的先进先出。如果刷完这四道题再把上面这些提上日程你对栈这个数据结构的理解会有一个质的提升。还有一点想多说两句力扣Hot100里的栈题目虽然不多但很多其他类型的题目内部也涉及栈的思想。比如二叉树的迭代遍历本质上就是用显式栈模拟系统栈的调用过程。理解了栈的“压入/弹出/回溯”语义遇到这类题目就能快速反应。8. 我的刷题体会与一些小建议这期总结写到这里按惯例聊聊我自己的体会。我刷Hot100有一个原则不追求刷题数量追求对每一道题的深入理解。栈这一组四道题如果只是走马观花看一遍题解可能半天就忘了。但如果自己手写代码把边界条件逐一测试再横向对比这四道题的内在逻辑收获会完全不同。拿我自己来说我刷有效的括号的时候第一次提交就通过了但代码写得很啰嗦用了三层if-else。后来看了题解里HashMap ArrayDeque的写法才意识到自己思路是对的但代码可以更优雅。从那以后我刷题会刻意追求简洁的写法不是为了炫技而是因为简洁的代码更能体现对问题的理解深度。另外一个心得是刷题不要只盯着AC。提交通过只是第一步第二步是思考时间复杂度能否优化第三步是想想有没有其他解法。最小栈如果用差值栈空间复杂度可以优化到O(1)限制在数据范围有限的情况下。字符串解码如果数据规模更大、嵌套更深可以用迭代加深的递归思想处理。多角度想一遍会加深对题目的理解。最后分享一个实用的小技巧在力扣上刷Java题可以顺手开启“调试模式”打印一下关键变量的变化过程。我调试字符串解码的时候就是在每个]处打印栈顶弹出的数字和拼接后的字符串一下子就看清了流程。复杂的逻辑加上一两行调试输出排查问题的速度会快非常多。栈这个专题就先写到这了。后面我打算按照同样的方式把Hot100的链表专题、二叉树专题也总结一轮把每一类数据结构的经典考法都梳理清楚。如果你也在刷这些题希望这期总结能给你一些参考价值。我们下一篇见。