★ FEATURED ARTICLE 如果让我在LeetCode Hot 100里挑一类“性价比最高”的题型栈绝对能排进前三。它的数据结构定义非常简单就是后进先出可刷题时却演化出了括号匹配、最小栈、单调栈、表达式求值等一大把花样。Hot 100里的栈题从简单到困难全覆盖从20题有效的括号到84题柱状图中最大的矩形、42题接雨水恰好串起了一个面试者从入门到进阶的完整路径。这类题不像动态规划那样需要很强的抽象建模能力也不像图论那样对模板积累要求高但它在“对未处理状态的维护”这件事上考察得非常深入而这一点在工程开发里其实特别常见。这篇文章我就把Hot 100里和栈强相关的题目打成一捆按“题型→解法→易错点”的脉络拆开讲适合想在面试前快速拿下栈、又不想漫无目的刷题的人。1. 为什么Hot 100的栈题值得专门刷1.1 栈的核心语义维护“最近未处理”的状态栈的核心操作其实只有两个push 入栈、pop 出栈而且只能碰栈顶。这个限制看起来很简陋但它对应的思维模式非常普遍——我们总是需要先处理那个“最近出现、还没处理完”的东西。浏览器后退按钮、编译器的括号配对、表达式求值时的运算优先级底层全是后进先出。在算法题里栈最擅长处理三类结构。第一类是对称/成对结构最典型的就是括号匹配。最近出现的左括号应该和最近出现的右括号配对这种“就近配对”用栈来表达再自然不过。第二类是嵌套结构。递归、嵌套括号、多层包裹的表达式内层状态永远比外层后出现但也先完结于是内层先入栈、先弹出完全符合栈的时序逻辑。第三类是序列的左右边界问题。单调栈可以在 O(n) 时间内找到每个元素左边或右边第一个比它大或小的位置这类问题用暴力解法往往要 O(n²)而栈能把重复的比较过程压缩掉。有意思的是很多看起来不沾边的题换个角度都能归到这三类里。树的遍历就是一个典型例子递归版本其实是系统在替你维护函数调用栈迭代版本则是想明白什么时候该手动入栈。再比如带括号的四则运算本质上就是把“暂时算不了”的子表达式压进栈里等到括号闭合或运算符优先级允许时再弹出来计算。所以栈不是某一个特定题型的专属工具它更像是算法里很底层的一种状态管理方式。我习惯给新手打一个比方栈就像叠盘子后叠上去的盘子一定是先拿走的你手头能碰到的永远只有最上面那个。算法题里那个“最上面的盘子”就是当前最需要被处理的位置。如果你能一直想清楚这个问题栈题基本就通了。1.2 栈题在Hot 100里的分布与难度梯度Hot 100里和栈强相关的题目大致是下面这8道题号题目难度核心考点是否依赖单调栈20有效的括号简单栈基本操作 哈希映射否155最小栈简单辅助栈 / 同步最小值否232用栈实现队列简单双栈模拟否150逆波兰表达式求值中等栈模拟计算否394字符串解码中等栈存状态 / 嵌套展开否739每日温度中等单调栈是84柱状图中最大的矩形困难单调栈 哨兵是42接雨水困难单调栈 / 双指针是为什么会把42题接雨水也放进栈专题里因为它虽然在Hot 100的标签里同时挂着数组、双指针、单调栈但在栈的解法里它的核心思路和84题非常接近都是在找左右边界区别只在于一个是求矩形面积一个是求积液量。把这两道题放一起啃效率比单独刷高得多。很多人在Hot 100里会跳过难题但栈这一块我强烈建议把84和42都拿下因为它们是单调栈真正发挥威力的地方。这8道题还有一个共同点都不需要复杂的数据结构支撑一个数组加一个栈就够了。真正的分水岭在于“栈里到底存什么”。到底是存下标、存数值还是存一个完整的Pair状态很多人一上来就背单调栈模板结果题一变就懵。我刷这部分时的策略是不看一道记一道而是把题目按“栈里装了什么”来归类。接下来我就按照这个思路把常用的题型套路过一遍。2. 栈题三件套括号、辅助栈、单调栈该怎么学2.1 括号类匹配、嵌套与状态循环括号题是栈题里的基础分核心规律只有一个遇左括号入栈遇右括号就检查栈顶是不是匹配的左括号匹配则弹出不匹配或者栈空则直接返回非法。括号题的难点其实不在代码而在一个容易忽略的点不要把“匹配”理解成“计数”。我见过不少人拿leftCount和rightCount去做遇到([)]这种交叉字符串就会挂。因为括号匹配是一个强调顺序的过程只能就近闭合。(匹配到的一定是离它最近的)中间夹了其他括号也必须先被处理完。计数只能知道数量相等不能知道顺序对不对。所以栈天然契合这种“最近匹配”模型。一个常见的优化是配合哈希表使用把右括号映射到左括号pairs {): (, ]: [, }: {}这样在匹配时就不用写三个 if 分支代码也更整洁。一旦熟悉了这道题后面遇到括号生成、删除无效的括号、字符串解码这类带嵌套的问题都会有共同的直觉凡是需要“回头处理之前出现过但还没闭合的东西”先想栈。2.2 辅助栈在一个栈之上叠加记忆辅助栈听起来高级其实就是“用一个额外的栈去记录历史信息”。最小栈是最经典的例子普通的栈可以随时返回栈顶但如果你想在 O(1) 时间内返回栈内最小值只靠一个栈就做不到。原因是 pop 可能会把当前最小值弹出去一旦弹走了你就不知道新的最小值是多少了。解决办法就是开一个辅助栈专门记录“从栈底到当前位置的最小值快照”。每次入栈时把min(当前入栈元素, 辅助栈栈顶)也压进辅助栈每次出栈时两个栈同步弹出。这样不管主栈怎么折腾辅助栈栈顶永远保持着“当前所有元素里的最小值”。辅助栈和单调栈有一个本质区别辅助栈里记录的是历史极值它不一定维护有序性单调栈则强制栈内元素单调递增或递减。很多人在最小栈里乱用单调栈觉得“反正都是栈套栈”其实思路完全不同。辅助栈重在“同步记录状态”单调栈重在“比较结算答案”。后面第三部分我会用具体题目把这层区别讲透。2.3 单调栈一套模板吃遍“下一个更大/更小”单调栈可以说是栈题里最值得花时间的一块Hot 100里的中级和困难栈题基本全是单调栈。它的思路很朴素维护一个栈让栈内元素从栈底到栈顶保持单调性。每来一个新元素就不断把破坏单调性的栈顶弹出直到重新满足单调为止。弹出这个动作本质上就是“栈顶元素的答案被结算了”。比如求“下一个更大元素”如果栈保持递减那么当前元素比栈顶大的时候栈顶的下一个更大元素就是当前这个元素。你只需要在弹出时记一笔答案即可。单调栈有一个非常统一的模板stack [] for i in range(n): while stack and 当前元素与栈顶元素破坏了单调性: idx stack.pop() # 在这里结算以 idx 为基准的答案 stack.append(i)这里有一个极其重要的细节栈里通常存下标而不是存值。原因有三第一通过下标可以随时拿到原数组的值第二结算答案时往往需要计算下标之间的距离第三只存值的话遇到重复元素或者需要回退计算时非常被动。比较符的选择也要小心。求“下一个更大”时我们要维护单调递减栈所以弹出的条件是当前值 栈顶值。求“下一个更小”时相反维护单调递增栈弹出的条件是当前值 栈顶值。至于等于的情况用不用等号取决于题目要求的是严格大/小还是非严格大/小。这个细节很多人栽过后面我会单独列一个避坑清单。3. Hot 100核心题目逐个拆解3.1 有效的括号五分钟拿下的基础分这道题不用多解释直接上代码def isValid(s: str) - bool: if len(s) % 2 1: return False pairs {): (, ]: [, }: {} stack [] for ch in s: if ch in pairs: if not stack or stack[-1] ! pairs[ch]: return False stack.pop() else: stack.append(ch) return not stack说几个容易忽略的点。第一长度是奇数直接返回 False这是一个收益极高的剪枝。字符串遍历还没开始已经把一半的用例挡在门外了。第二空栈判断。很多新手在检查右括号时直接写stack[-1] pairs[ch]如果这时候栈是空的就会报错。更严谨的写法是if not stack or stack[-1] ! pairs[ch]先用短路的not stack兜底。第三最后返回not stack而不是True。因为可能出现(()这种左括号没有弹完的情况这时栈不为空说明字符串非法。这段代码的时间复杂度是 O(n)n 是字符串长度空间复杂度最坏也是 O(n)。这道题是热身赛只要能把上面几个点说明白就算过关了。3.2 最小栈辅助栈的教科书最小栈要求的是一边执行 push、pop、top一边还能在 O(1) 时间内返回最小值。直接开一个辅助栈的思路我已经在2.2节讲过。这里给完整实现class MinStack: def __init__(self): self.stack [] self.min_stack [] def push(self, val: int) - None: self.stack.append(val) if not self.min_stack or val self.min_stack[-1]: self.min_stack.append(val) def pop(self) - None: if self.stack.pop() self.min_stack[-1]: self.min_stack.pop() def top(self) - int: return self.stack[-1] def getMin(self) - int: return self.min_stack[-1]这个实现里藏着一个非常经典的坑辅助栈的入栈条件必须是不能是严格。因为如果存在重复的最小值比如连续 push 两个相同的1辅助栈只在第一次入栈时记录了1第二次因为val 栈顶为假就没入栈。之后主栈第一次 pop把栈里的1弹掉同时辅助栈也把唯一的1弹掉主栈里明明还有一个1但getMin()已经拿不到1了栈为空会直接报错。所以重复值必须同步记录。这个细节如果面试时你能主动讲出来是非常加分的。进阶版本可以用一个栈存差值来压缩空间核心思想是把val - min存进栈里通过差值正负来判断是否更新最小值。但这个方案在差分值接近整型边界时有溢出风险面试时如果为了炫技反而容易翻车。我的建议是默认就写双栈简洁、稳妥、可解释。3.3 每日温度单调栈的入门练习题目给一组每日温度要求返回一个数组每个位置表示“要等多少天才能等到一个更高温度”。暴力解法是每个位置向右扫描最坏 O(n²)。但用单调栈可以做到 O(n)。我的写法是正向遍历维护一个递减栈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]]: prev stack.pop() ans[prev] i - prev stack.append(i) return ans栈里存的是下标且从栈底到栈顶对应温度是递减的。每到一个新下标 i只要当前温度高于栈顶下标对应的温度就说明栈顶元素已经找到了它右边第一个更高的温度答案就是i - prev。这个元素出栈之后新的栈顶继续参与比较直到栈空或当前温度不足以继续弹出。这句话是理解单调栈的关键每个元素只会入栈一次、出栈一次所以整个算法是 O(n)。这就是单调栈把暴力解法里重复扫描的部分一次性摊销掉的原因。这道题的常见错误是栈里存了温度值而不是下标。存值虽然能比较出来大小但答案要求的是“天数差”没有下标就根本算不出来。所以要么再开一个(value, index)的结构要么干脆只存下标通过temperatures[stack[-1]]去取值。我推荐后者干净利落。3.4 字符串解码栈与状态的嵌套字符串解码题看起来复杂但核心模式和括号题一模一样遇到[把当前状态压栈遇到]把栈里的状态弹出来还原。我用的解法是“单栈 逐字符推进”def decodeString(s: str) - str: stack [] for ch in s: if ch ]: part [] while stack and stack[-1] ! [: part.append(stack.pop()) stack.pop() # 弹出 [ num_str [] while stack and stack[-1].isdigit(): num_str.append(stack.pop()) repeat int(.join(reversed(num_str))) stack.append(.join(reversed(part)) * repeat) else: stack.append(ch) return .join(stack)以3[a2[c]]为例走一遍先入栈3、[、a、2、[、c。遇到第一个]先把c弹出来然后弹掉[接着往回读数字2得到c * 2 cc压回栈。这时栈里是3, [, a, cc。再遇到第二个]弹出a和cc拼成acc弹掉[往回读数字3得到acc * 3 accaccacc压回栈。最后把栈里的元素拼起来就是答案。这里有一个容易踩的坑数字不一定只有一位比如12[a]。所以读数字时必须连续弹出所有数字字符再反转拼成整数不能只读一位就停。还有一点值得注意这道题的时间复杂度不是简单的 O(n)。因为展开后的字符串长度可能远大于输入长度输出本身就有O(输出长度)那么大所以任何解法都要付出这个下限成本不用因为这个感到焦虑。3.5 困难题两座大山柱状图最大矩形与接雨水终于到了单调栈的高阶部分。说难其实不难但这两道题对“栈里存下标 哨兵”这套技巧要求很高。先看84题柱状图中最大的矩形。核心思路是枚举每个柱子作为矩形的高度向左向右扩展到第一个比它矮的位置这两个位置之间的宽度乘以当前高度就是以它为高度的最大面积。问题是怎么快速求出每个柱子的左右边界单调递增栈可以做到。如果维护一个递增栈那么每当一个新柱子比栈顶矮栈顶柱子就再也不能向右扩展了它的右边界是当前下标 i左边界是弹出它之后新的栈顶下标。宽度就是i - left - 1。完整代码def largestRectangleArea(heights: List[int]) - int: heights.append(0) # 哨兵强制最后把所有矩形结算完 stack [] ans 0 for i in range(len(heights)): while stack and heights[i] heights[stack[-1]]: h heights[stack.pop()] left stack[-1] if stack else -1 ans max(ans, h * (i - left - 1)) stack.append(i) return ans末尾补一个高度为0的哨兵是这道题的灵魂。它保证了遍历结束后栈里不会残留任何柱子因为0比任何正数都矮会把所有剩余柱子全部弹出结算。如果不加哨兵你还得在循环结束后再单独写一段清理逻辑代码立刻复杂很多。有人会问如果柱子高度有重复怎么办比如[2,2,2]。我用的是而不是也就是重复高度不会立即弹出但结算时因为高度一样宽度可能算大了也不会影响最终答案因为相同高度取最宽的那个才是正确答案。写成也可以两种版本都能过关键是你要清楚自己用的是哪种比较方向。42题接雨水思路和84题一脉相承只是单调方向反过来了。这道题用单调递减栈当前高度比栈顶高时栈顶就形成了一个凹槽的底部新的栈顶是左墙当前 i 是右墙积水体积就是宽度 × 左右矮墙与底部的高度差。def trap(height: List[int]) - int: ans 0 stack [] for i in range(len(height)): while stack and height[i] height[stack[-1]]: bottom stack.pop() if not stack: break left stack[-1] w i - left - 1 h min(height[left], height[i]) - height[bottom] ans w * h stack.append(i) return ans注意这里的宽度计算w i - left - 1因为左右墙的下标差减一才是中间能存水的格子数。另外当bottom弹出后如果栈空了说明左边没有墙那这个位置无法积水直接break跳出 while但仍然会把当前的 i 入栈作为新的墙。这两道题放在一起记忆效果很好84题是“弹出低处计算向外扩展的面积”42题是“弹出凹处计算向内接住的水量”。它们就像单调栈的一体两面一个向右找边界一个向左找边界但模板结构完全一致。4. 刷栈题踩过的坑边界条件与调试技巧4.1 最容易翻车的四个边界我按出现频率排个序每个都是实战中真正遇到过的。一是空栈问题。在右括号、单调栈弹出的过程中“先判断空再访问栈顶”是铁律。任何形式的stack[-1]之前都要想一下栈会不会是空的。二是比较符的严格与非严格。求“下一个更大元素”时栈顶严格小于当前元素才弹出等于时不弹出保证答案是严格更大。求“下一更大或相等”时就换。84题里重复高度的场景我用但很多人习惯用两种都行但建议固定一套避免临场混乱。三是哨兵放开头还是结尾。84题要把哨兵放在数组末尾用来保证所有柱子被弹出。有些题比如包含负数或需要前缀处理的哨兵可能放在开头更合适。先把需求想清楚再决定放哪。四是最小栈的相等值。我在3.2节已经强调了辅助栈入栈必须是。这个坑出现的频率比你想的高得多。4.2 用数组模拟栈还是语言自带栈面试和笔试场景下语言自带的栈接口其实完全够用。Python就用listappend()和pop()天然是栈操作而且list[-1]访问栈顶非常顺手。C就用stackintJava用Deque。不过有时候我会故意用数组模拟栈尤其是写84题和42题这种需要往回看的题。数组模拟的好处是可以随机访问栈内任意位置方便打印中间状态出问题调试也更直观。C里很多人直接用vectorint stk;代替stackint因为它同时支持push_back、pop_back、back()本质就是栈但还能拿到所有元素。这不影响正确性但调试体验好很多。另外递归其实也是一种栈函数调用栈的深度在极端用例下会爆掉。比如二叉树深度一万层的遍历递归版可能直接栈溢出手动栈迭代版反而稳稳当当。所以树相关题目如果允许我经常优先写迭代栈版本风险更小。4.3 一道题从暴力到最优的演进思路单调栈的模板可以背但面试时面试官真正想听的往往是你怎么想到用栈的。以42题接雨水为例一个完整的演进叙事应该是先是暴力法。对每个位置 i分别扫描左侧和右侧找到最高墙当前列能接的水是min(leftMax, rightMax) - height[i]。这需要 O(n²) 时间但思路最直白。然后是预处理优化。先从左到右扫一遍记录每个位置的左侧最高墙再从右到左扫一遍记录右侧最高墙。这样每个位置查表即可时间降到 O(n)空间 O(n)。这就是动态规划的前缀/后缀最值思想。最后才是单调栈。在观察中发现扫描过程里很多墙的高度信息其实可以放在栈里复用因为“当前的墙到底能不能积水只取决于它和两侧墙的相对高低”。于是用递减栈维护墙的下标一遍扫描完成结算。空间还是 O(n)但状态流转更符合“遇到一个更高的墙就结算一段积水”的自然过程。这个演进过程非常重要。它证明你不是在背题而是真的理解“为什么用栈”。我建议你在刷84题时也这么做一遍先写暴力 O(n²)再写单调栈 O(n)感受一下重复计算是怎么被省掉的。5. 栈题的面试实战与进阶思考5.1 拿到一道栈题的解题节奏面试时候我一般会按这样的顺序推进。第一步先复述题意把输入输出和边界条件确认清楚。比如“字符串里只包含三类括号吗”“温度数组可能为空吗”这些问题能帮你避开很多实现雷区。第二步先讲暴力解法。不要觉得暴力解法低级它能证明你的基础理解是对的而且往往是通往最优解的最短路径。比如84题暴力解法只需要枚举每个柱子的高度并向两边扩张大家一听就懂。第三步再讲如何优化。指出暴力解法中有大量重复扫描而这些重复可以通过维护一个递增/递减栈来消除。这句话就是把单调栈引出来的关键台词。第四步开始写代码前口头说明“栈里存下标”。这一步别看简单提前说出来会让面试官觉得你是真懂而不是在默写模板。第五步写完后一定拿个示例手动跑一遍。比如heights [2,1,5,6,2,3]把每次入栈、弹出、结算面积的过程写出来确认代码没有明显逻辑问题。这个习惯在面试里非常加分。第六步主动说出时间复杂度和空间复杂度顺带提一下哨兵的作用。5.2 栈的本质递归、DFS 与状态管理的暗线栈不仅在括号、温度这类直白场景里出现它还暗藏在许多算法里。递归就是函数调用栈DFS本质上是显式或隐式地用栈维护“待访问路径”回溯也是撤销上一次选择这种撤销操作完全符合栈的语义。所以把栈题刷透等于同时把递归、DFS、回溯的基础打牢了。在Hot 100的后续刷题里你还会遇到很多栈题的表亲比如下一个更大元素它可以在循环数组中用单调栈加“翻倍数组”的技巧处理再比如基本计算器、逆波兰表达式求值它们和字符串解码用的是同一套“状态入栈、闭合结算”框架。刷完Hot 100的栈题后再用这些题做扩展会非常顺畅。我自己的体会是栈题难的不是语法而是状态。最开始刷84题时我也是反复看题解想不明白为什么弹栈的一瞬间就算出面积了。后来我拿一个具体例子把每一步入栈、出栈后的栈内容画在纸上才算真正建立起了直觉。所以上面这些代码我建议你一定不要只是读一遍而是找几个用例把栈的每一步手动模拟一遍。比如用heights [2,1,5,6,2,3]跑84题用s 3[a2[c]]跑字符串解码写一遍比看十遍都管用。栈这种数据结构看着简单但把它练到条件反射的程度靠的就是这种笨功夫。
阅读完成 · 觉得有帮助？
