最近把 LeetCode 上栈相关的题目集中刷了一遍从最基础的括号匹配到单调栈、表达式求值再到把递归改成迭代的二叉树遍历一路刷下来最大的感受是栈这个结构看着简单但玩法真的很多。很多题目表面包装得很花哨剥开之后核心思路往往是同一套。这篇刷题日记就专门整理栈类题目的常见题型、解题套路和实战中容易踩的坑适合刚开始刷题的新手也适合准备算法面试前想快速梳理重点的老手。不管你是用 Python、Java 还是 C核心思路都是通用的照着这套框架去归纳总结效率会高很多。1. 栈类题目的整体框架与题型划分1.1 栈的三条核心特征先花一分钟把栈的本质说清楚。栈就是一个后进先出的线性表只有栈顶能操作push放进去、pop拿出来peek只看不取。你可以把它想象成一叠盘子你永远只能先拿走最上面那个后来放上去的反而最先被取走。这条性质决定了栈最适合处理三类场景第一类是嵌套成对结构比如括号([{}])后面的右括号要先和最近的左括号匹配天然符合后进先出第二类是需要回退最近状态的场景比如函数调用栈比如撤销操作栈顶永远保存着“最近发生了什么”第三类是寻找最近更大/更小元素的描述型问题后面会重点讲单调栈几乎就是为此量身定做的。刷题时脑子常备这三条特征看到题目描述就能快速判断这是不是成对匹配这是不是要用到历史状态这是不是要找下一个更大更小命中任意一条栈就该上场了。1.2 栈题常考题型速览表我在刷题过程中把常见栈题分成了六类整理成一张表供参考题型分类代表题目方向核心考点括号匹配类判断有效括号、最长有效括号对称性、配对规则、栈顶匹配单调栈类每日温度、下一个更大元素、柱状图中最大矩形单调性维护、存索引而非存值栈模拟递归二叉树先序/中序/后序迭代遍历、DFS 显式化理解递归本质、手动维护调用栈栈设计题最小栈、用两个栈实现队列辅助栈思想、状态同步表达式求值类逆波兰表达式求值、基本计算器双栈法、运算符优先级出入栈序列判断栈的压入、弹出序列模拟进出栈全过程这六类不是完全独立的比如括号匹配也可以归到“模拟”大类里单调栈在矩形面积和接雨水里又会结合边界思想。表格的意义在于让你先有一个全景图刷题时能定位自己练的是哪一类而不是做完一题忘一题。1.3 判断“要不要用栈”的快速信号除了上面三条特征我还总结了一些具体信号。如果题目里出现**“成对”“匹配”“嵌套”“最近”“回退”“DFS”“合法括号”“下一个大于/小于”“逆波兰”**这些高频词大概率能往栈方向想。举个例子看到“给定一个只包括()[]{}的字符串判断是否有效”嵌套匹配四个字直接写成答案。看到“返回一个数组其中每个元素是下一个比它大的元素”这就是单调栈的嗅觉信号。看到“用栈来模拟递归”或者“层序遍历的迭代写法”本质上也是栈和队列的选择题。信号这种东西不玄学你只需要在刷题时多追问一句“为什么这道题会想到栈”积累二十道之后这种直觉自然就出来了。2. 括号匹配栈题当之无愧的第一课2.1 为什么括号匹配总能想到栈括号匹配是我认为最适合作为栈入门的第一类题。原因很简单括号对的结构就是最近的左括号必须对应最近的右括号这种精确的“嵌套对称”关系和栈后进先出的逻辑完全重合。想象一下字符串{ [ ( ) ] }当遇到第一个右括号)时它要匹配的左括号(正是最近进入栈的那个元素匹配完()后问题缩小到{ [ ] }接下来右括号]要匹配最近的左括号[。这就像剥洋葱一层一层从里往外剥每一层都在回溯最近状态栈天然把这个过程模拟得明明白白。2.2 有效括号的完整实现“有效括号”LeetCode 20的解法长这样我直接给出 Python 版本def isValid(s: str) - bool: stack [] pairs {): (, ]: [, }: {} 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几个关键细节值得展开说第一为什么用字典映射因为左括号有三种右括号也有三种如果用elif挨个判断代码会又长又容易漏。字典把“右括号 - 对应左括号”的关系集中管理遇到右括号直接查表非常干净。第二为什么访问栈顶前必须先判空stack[-1]在空栈上会直接报错。真实输入可能上来就是]栈是空的这时候根本没有栈顶可以检查必须先if not stack判断。这个坑在后面的栈题里会反复遇到。第三为什么最后要return not stack有人会漏掉这个判断认为只要遍历过程不出错就行了。但输入(((遍历完所有左括号都入栈全程不会有任何出栈动作如果不检查栈是否为空就会被误判为有效。字符串遍历结束后的清空校验是这道题最容易丢分的地方。复杂度方面每个字符最多入栈一次、出栈一次时间 O(n)空间最坏 O(n)。2.3 括号类变体题目最长有效括号与括号生成基础题之外还有两个常见变体我简单说下思路。最长有效括号LeetCode 32是“有效括号”的进阶版它要求返回最长连续有效括号子串的长度。核心思路是栈里存索引而不是字符因为你需要用索引下标来计算长度。做法是在栈底先压入一个-1作为哨兵遇到左括号压入当前下标遇到右括号弹出栈顶。弹出后如果栈为空说明当前这个右括号没有配对的左括号就以它为新的起点压入下标如果栈不为空就用当前位置减栈顶位置得到当前有效长度不断更新最大值。这个“索引入栈 哨兵”的技巧很值得背下来。括号生成LeetCode 22虽然主流做法是回溯但生成过程中判断“还能不能放右括号”时本质也是维护左右括号的配对数量关系。这类题对培养括号类题目的敏感度很有帮助刷完基础版顺手做做即可。3. 单调栈面试最爱考的进阶栈题型3.1 单调栈解决什么问题括号匹配之后栈题的下一个台阶就是单调栈。单调栈说白了就是栈内元素保持单调递增或单调递减的栈它的用途非常专一快速找到每个元素左侧/右侧第一个比它大或比它小的元素。暴力做法是什么双重循环对每个元素往右看找到第一个更大的就停止时间复杂度 O(n²)数据量一大就完蛋。单调栈的做法是 O(n)因为每个元素最多入栈一次、出栈一次。打个生活化的比方想象操场上一排学生排队老师站在末尾问“每个人的右边第一个比自己高的人是谁”。暴力做法是每个人依次往后看有人个子越往后越看不到单调栈做法则像一个智能淘汰机制——一旦出现一个更高的新人前面所有低个子的问题一次性答复完毕然后低个子出局因为他们的“下一个更高者”已经确定继续留着也没意义了。这个机制在算法层面就是 while 循环的弹栈过程。3.2 下一个更大元素的基本模板下面这段代码是“下一个更大元素”的核心模板把这段啃透你会发现很多题目只是换皮def nextGreaterElement(nums): res [-1] * len(nums) stack [] for i in range(len(nums)): # 当前元素比栈顶索引对应的元素大说明栈顶找到了答案 while stack and nums[i] nums[stack[-1]]: idx stack.pop() res[idx] nums[i] stack.append(i) return res重点在于栈里存的是索引不是元素值。为什么因为题目要求返回和原数组等长的结果数组你需要知道“谁找到了答案”以及“答案是什么”。存索引可以同时拿到下标和值res[idx] nums[i]一句两得。存值的话定位不了位置后患无穷。整个过程的维护策略是从栈底到栈顶严格递减。新元素到来只要它是更大的就会把栈里所有比它小的元素全部弹出这些被弹出的元素遇到的就是“下一个更大元素”。处理完弹栈后当前元素入栈等待它自己的“下一个更大者”。拿[2, 1, 3]手动演算一遍初始stack []res [-1, -1, -1]。遍历到2栈空入栈索引0。遍历到11 nums[0]2不成立不弹栈入栈索引1。此时栈底到栈顶为[0, 1]对应值[2, 1]满足递减。遍历到33 nums[1]1弹出索引1res[1] 3继续比较3 nums[0]2弹出索引0res[0] 3。最后入栈索引2。最终结果[3, 3, -1]。末尾剩下的元素例如最后的3右边没有更大者保持默认的-1。3.3 变体一每日温度与循环数组“每日温度”LeetCode 739几乎是同一个模板。题目要求的是“对于每一天至少等多少天才能等到一个更高温度”本质就是“下一个更大元素”的距离版本。依然维护递减栈栈中存索引。弹出栈顶时不再记录温度而是记录天数差def dailyTemperatures(temperatures): res [0] * len(temperatures) stack [] for i in range(len(temperatures)): while stack and temperatures[i] temperatures[stack[-1]]: idx stack.pop() res[idx] i - idx # 等待天数 当前下标 - 栈顶下标 stack.append(i) return res这里为什么必须存索引因为要计算天数差只有索引能给出两个日期之间的距离。这类“距离敏感”的题目几乎都要优先考虑把索引作为栈元素。如果遇到循环数组比如“下一个更大元素 II”解法也不复杂遍历两遍数组用i % n取模构造循环。第二遍遍历时栈里还可能残留一些在第一遍中没找到答案的元素继续处理即可。循环场景的核心不是真的要复制数组而是通过取模让索引循环跳转代码省事很多。3.4 变体二柱状图中最大的矩形与接雨水这两道是单调栈里的硬核题硬核在于除了单调性还要维护边界宽度。“柱状图中最大的矩形”LeetCode 84的思路是遍历每个柱子高度维护递增栈。当遇到比栈顶高度小的柱子时弹出栈顶此时弹出的柱子高度为h它能形成的最大矩形宽度就是“从弹出后的新栈顶 1 到当前柱子索引前一位”的距离。为什么因为新栈顶是左边第一个比它矮的柱子当前柱子是右边第一个比它矮的柱子左右两堵“矮墙”之间——注意是开区间区间宽度乘h就能算出以该柱子为最低高度的最大矩形。“接雨水”LeetCode 42的单调栈版本类似当当前高度大于栈顶高度时弹出栈顶元素作为凹槽底部此时新栈顶和当前元素就是左右边界三者之间能积的水量等于min(左边界, 右边界) - 底部高度再乘以宽度。这类题我建议画图理解把柱子画出来在图上标出出入栈顺序一遍就能看懂。别一上来就硬记代码。4. 栈与递归、DFS换个姿势看同一件事4.1 函数调用本来就是栈很多同学学二叉树遍历时对递归版烂熟于心但一看迭代版就头晕。归根结底是因为没意识到递归的本质就是调用栈。每次递归调用系统都会把当前函数的局部变量、返回地址压入栈中函数返回时再从栈顶恢复现场。显式地用一个栈来模拟递归不仅是把电影翻拍成小说换个表达方式最大的现实好处是避免递归深度过大导致的调用栈溢出。工程上一些极端条件会明确禁止递归实现这时候迭代版就是保命技能。从面试角度说向考官展示“我能用栈手动模拟函数调用过程”也说明你对递归原理有更深的理解。4.2 二叉树的先序遍历递归版 vs 迭代版先序遍历的顺序是“根 - 左 - 右”。递归版很好写def preorder_recursive(root): if not root: return [] return [root.val] preorder_recursive(root.left) preorder_recursive(root.right)迭代版的核心是手动维护栈。代码长这样def preorder_iterative(root): res [] stack [root] while stack: node stack.pop() if node: res.append(node.val) # 注意先压右子树再压左子树 if node.right: stack.append(node.right) if node.left: stack.append(node.left) return res这里最容易问倒人的问题是**为什么先压右子树再压左子树**因为栈是后进先出你希望先访问左子树就要让左子树后进栈、先出栈。所以压栈顺序跟访问顺序相反right先进left后进循环时left优先弹出。这个“压栈顺序与输出顺序相反”的点在写迭代遍历时一定要刻在脑子里。中序遍历的迭代版稍微绕一点需要用一个cur指针配合栈沿着左子树一路入栈到底后开始回头访问def inorder_iterative(root): res [] stack [] cur root while cur or stack: while cur: stack.append(cur) cur cur.left cur stack.pop() res.append(cur.val) cur cur.right return res这个套路就是一路向左左到不能再左就弹出节点访问然后转向右子树。几乎每一棵二叉树的迭代中序遍历都是这个骨架。4.3 DFS 的栈实现与经典场景深度优先搜索DFS同样可以写成栈版本。经典场景比如“岛屿数量”LeetCode 200遍历到一块陆地后就沿着上下左右四个方向一直探索下去直到没有相邻陆地。这个“一条路走到底再回头”的行为和递归调用一模一样所以完全可以用显式栈替代递归避免岛屿规模巨大时发生栈溢出。用栈替代递归的框架通常长这样先把起点压入栈循环过程中从栈顶取出一个节点处理再把它的未访问邻居全部压入栈。注意这里和广度优先搜索的顺序恰好相反队列是先排先处理而栈会把最近压入的邻居先处理从而天然形成深度方向的探索。日常练习我建议把每个递归版 DFS 都手写一遍迭代版不为别的就为了通过对比彻底理解“函数调用栈 局部状态保存”这两个概念。理解了这个你再看动态规划那边什么记忆化搜索的递归转迭代也顺手很多。5. 最小栈、队列设计题与表达式求值综合运用栈的能力5.1 最小栈空间换时间的典范“最小栈”LeetCode 155要求实现一个栈支持入栈、出栈、取栈顶、取最小值四个操作且getMin要是 O(1)。朴素想法是每次调用getMin时遍历整个栈找最小值但这样查询是 O(n)面试通常不认。标准解法是空间换时间用一个辅助栈minStack同步记录每次入栈时的当前最小值。思路很简单每次push(x)时stack.append(x) # 辅助栈记录当前最小值 if not minStack or x minStack[-1]: minStack.append(x) else: minStack.append(minStack[-1])pop时两个栈同步弹出getMin直接返回minStack[-1]。辅助栈与主栈等长保证每个历史时刻的最小值都被记住了逻辑非常直白。不过这里有个小优化空间不存等长辅助栈而是只存“出现过的新最小值”弹出时判断是否等于栈顶最小值再决定是否弹出辅助栈。这样辅助栈通常更短代码稍复杂一丢丢。两种方案都可以确认自己理解了两种方案的差异即可。5.2 用两个栈实现一个队列“用栈实现队列”LeetCode 232也是一道很经典的设计题。栈是后进先出队列是先进先出看起来完全相反但用两个栈一倒腾就能实现。核心操作是入队直接push到栈inStack出队时先检查outStack如果outStack为空就把inStack里的所有元素依次弹出并压入outStack这样顺序就被颠倒了再从outStack弹出顶部元素即可。打个比方你有一摞盘子把盘子一个个从 A 堆搬到 B 堆B 堆里盘子的上下顺序和 A 堆完全相反。搬一次之后从 B 堆顶部拿走的正是 A 堆最底下的那只也就是最早放进去的那只先进先出就实现了。摊还分析下来每个元素最多被入栈出栈各两次整体 O(1)。这题对理解“为什么有些题需要两个栈/两个队列配合”很有帮助面试中会和后续讲的表达式求值双栈法形成呼应。5.3 表达式求值双栈法和逆波兰表达式表达式求值分为两类一类是直接给你逆波兰表达式另一类是给你常规中缀表达式。逆波兰表达式求值LeetCode 150非常直白遇到数字就压栈遇到运算符就弹出两个数字参与运算结果再压回栈。完整代码如下def evalRPN(tokens): stack [] for t in tokens: if t in -*/: b stack.pop() a stack.pop() if t : stack.append(a b) elif t -: stack.append(a - b) elif t *: stack.append(a * b) else: # 注意Python 的 / 是浮点除法需要 int 转为向零取整 stack.append(int(a / b)) else: stack.append(int(t)) return stack[0]两个细节值得提醒一是运算顺序a是第一次弹出的数b是第二次弹出的数做减法时是a - b别写成b - a二是 Pyhton 的/会得到浮点数而题目要求整除且向零取整所以要用int(a / b)做转换很多初学 Python 的在这里翻车。中缀表达式求值如“基本计算器”更复杂一些需要双栈一个数字栈、一个运算符栈。遇到数字进数字栈遇到运算符时先判断优先级如果当前运算符优先级不高于栈顶运算符就先取出栈顶运算符参与计算再把当前运算符压栈遇到右括号则一直弹运算符计算直到左括号弹出。这个流程建议写代码前先手动演算一遍3 2 * 2体会一下“乘法和加法同栈并存时乘法必须先算”的原因思路就顺了。6. 栈题常见错误与调试技巧实录6.1 空栈访问是头号错误刷栈题最常见的崩溃方式就是在空栈上调用pop()或peek()。不管是写stack[-1]还是stack.pop()只要栈是空的直接报错或返回错误结果。解决办法就一句话在任何弹栈或取栈顶操作前先判断栈是否为空。括号匹配里if not stack的判断、单调栈里while stack and的短路写法目的都是为了安全。写单调栈时我习惯把while stack and 条件作为模板固定写下来先保证不崩再想业务逻辑。如果你想加深印象可以故意构造这些用例跑一遍代码空字符串、单一右括号)、((((、)))。每个用例都能揪出一种隐藏问题。6.2 栈里存值还是存索引想清楚再动手栈元素可以是字符、整数、索引、甚至数组但选择什么类型通常决定了整道题的方向。如果题目只关心元素本身的值比如括号匹配只关心字符配对那直接存字符即可如果题目需要计算下标差、区间宽度、位置关系比如每日温度的天数差、柱状图的宽度那必须存索引。一旦存了索引想要获取值就用nums[stack[-1]]两个信息都握在手里。我踩过的一次坑是“下一个更大元素 II”一开始图省事存了值结果循环数组里相同值覆盖时根本没法定位位置最后改回存索引才解决。经验教训是拿不准的时候优先存索引信息越全后面改动代码越灵活。6.3 别被 while 循环吓到均摊复杂度是 O(n)很多同学第一次看单调栈代码看到一个 while 循环嵌套在 for 循环里第一反应是 O(n²)进而怀疑模板的正确性。实际上每个元素只会入栈一次也只会出栈一次while 循环里所有的弹栈加起来最多总共 n 次。整个算法的时间复杂度是均摊 O(n)。判断这类代码能不能用有一个简单的思路观察每个元素是否可能被多次处理。在单调栈模板里被弹出后的元素再也不会回到栈中不会再次出现在未来 while 的判断里。只要掐住“一次入栈一次出栈”这个事实复杂度的疑问自然就消失了。6.4 栈题的边界用例速查表边界情况容易出现的错误解决方法空输入一开始就访问栈顶判断输入长度为 0直接返回默认值全是左括号遍历结束栈非空却当作成功结束后校验栈是否为空全是右括号第一次右括号时栈空弹栈前判空单个元素数组单调栈末尾残留保持默认结果不要额外处理数值很大/很小溢出的潜在风险使用 Python/Java 大整数能力或用合适类型刷题阶段养成拿边界用例先测一遍的习惯会比盲目多刷几题更有价值。6.5 画图调试法栈题最实用的排障手段栈这东西非常抽象代码跑一遍结果错光看代码很难看出问题在哪。我的建议是拿一张纸把栈画成一个竖着的方框元素从上往下压遇到 push/pop 就沙盘演算一遍。拿单调栈画两个简单的数组迭代过程你会很快理解“下一个更大元素”里为什么栈会保持递减、为什么新大元素一到位就会连环弹出。画三遍之后脑子里的栈模型就建立起来了以后再遇到栈设计题、表达式求值题你甚至能从纸上“看到”代码该怎么跑了。刷完这批栈题我自己最大的体会是栈的题目并不难难的是识别出“这里要用栈”。一旦识别出来解法框架其实都是高度相似的——要么是括号配对要么是单调栈维护要么是模拟递归或表达式运算。最后再分享一个小技巧做栈题前先别急着写代码先在纸上演算一遍标准流程把中间过程和栈的状态写清楚再开始敲代码你会发现代码几乎一次通过调试时间至少省一半。