刷 Leetcode Hot 100 的都知道栈这一块儿看着题目不多但几乎每道题都能牵扯出好几个面试官爱问的考点括号匹配、单调栈、表达式求值、用显式栈模拟递归……标题里写个“栈”字翻译过来其实是“一类用后进先出思想解决特定子问题的套路合集”。这篇东西我打算直接按刷题实战的角度拆开讲不只是把题解列一遍更重要的是把“为什么这道题要用栈”“栈里到底存什么”“边界条件怎么抠”这几个核心问题说清楚。适合谁看两种人一种是刚开始刷 Hot 100碰到栈题总是一看就会、一写就废的另一种是栈题刷过几遍但碰到“基本计算器”这种中等偏上的题还是发怵的。我会用大量实际代码和逐步推演尽量让你看完能直接上手复现。栈这个东西本质上就是在帮你记住“之前发生的事”所有的题目变体都绕不开这个内核。1. 为什么栈在 Hot 100 里这么重要——先搞懂它到底在解决什么问题很多人把栈理解成“一种只能从顶部操作的数据结构”这没错但太表面了。你真正应该记住的是栈解决的是“需要回溯、需要记住最近状态、需要按嵌套顺序处理”的一类问题。Leetcode Hot 100 里凡是能用栈解的题几乎都满足这个描述。1.1 栈的抽象模型后进先出到底意味着什么拿日常生活中的叠盘子来类比你往桌上一张一张叠盘子最后放上去的盘子永远是第一个被拿走的。这个“后进先出”的特性决定了栈天然适合处理具有嵌套结构、对称结构、或者需要逆序处理的数据。在算法题里这个模型有几个具体的表现形式配对消除比如括号、HTML标签、路径里的..遇到配对的就消除栈天然是“记录左边、遇到右边就检查”的容器。最近相关性比如“下一个更大元素、每日温度”你要找的是“当前元素右边第一个比它大的”这要求你记住已经遍历过但还没处理完的元素而且越是“最近”的元素越先被处理。显式记忆现场递归函数本身用的是系统调用栈当你想把递归改成迭代、或者控制递归的深度和方向时你手动维护一个栈就能模拟系统栈的行为。表达式求值括号的嵌套、运算符的优先级本质上是两三种不同“上下文”的切换栈能在不同层级之间来回跳。热词里提到的“backtrace栈回溯”和“栈帧形成过程”其实就是从系统层面印证了这套思想程序运行时每次函数调用都会在调用栈上压入一个栈帧函数返回时栈帧弹出整个调用链就是一棵回溯树。你刷题用的栈跟系统调用栈是同构的只是你把这个机制显式地拿出来了。1.2 Hot 100 中栈题目的分布与共性Hot 100 里直接标注“栈”标签的题大概二十多道但实际用栈作为最优解的题还包括一些容易忽略的比如“反转链表”可以用栈实现、“二叉树的中序遍历”显式栈版本。我做了一个粗略归类题型归类典型题目栈的角色括号与配对消除有效的括号、最长有效括号记录左括号位置延迟匹配单调栈每日温度、下一个更大元素、柱状图中最大的矩形维护一个有序的候选集表达式求值基本计算器、逆波兰表达式求值保存数字和运算符处理优先级显式栈模拟递归/回溯二叉树遍历、字符串解码、迭代法求子树替代系统调用栈栈与队列互转用栈实现队列、用队列实现栈用两个栈倒腾顺序共性很明显凡是栈题解题的关键一定不是“你会不会用栈”而是“你决定栈里存什么、什么时候入栈、什么时候出栈、出栈时做什么”。这四个问题想清楚了代码只是顺手的事。1.3 为什么“单调栈”能比暴力快这么多Hot 100 里有好几道单调栈的题很多人初看时觉得没必要搞懂暴力双循环也能过为什么还要维护一个单调栈答案是时间复杂度从 O(n²) 降到 O(n)。打个比方暴力法相当于你每次站在一个位置问“我右边有没有比我高的”每次都往后扫一遍单调栈则相当于你手里拿着一张“待解决名单”每当新元素进来就把名单里那些已经被解答的人划掉。每个人最多入栈一次、出栈一次所以总时间是线性的。这个思想在很多非栈题里也会出现比如滑动窗口最大值、接雨水Hot 100 里接雨水的双指针/单调栈解法都值得研究。所以我会说单调栈是你在 Hot 100 栈题里最值得花时间啃透的一个点。2. 栈类题目的四种核心模式以及怎么一眼识别刷题刷多了你会发现栈题基本就是四个套路。看清题目长什么样就能立刻知道该用哪个套路这是提高效率的关键。2.1 配对消除模式遇到“对称结构”先想到栈这种模式的特点是输入是一串有配对规则的元素你需要处理嵌套或前后关联。最典型的就是括号。识别特征也很简单题目出现了()[]{}、成对的begin/end、或者是“消除相邻重复项”这类词。核心写法模板def helper(s): stack [] for c in s: if c 是左半部分: stack.append(c) else: # 这里是一个关键点先判空 if not stack or stack[-1] ! 匹配的右半部分: return False stack.pop() return not stack # 结束之后栈必须为空一个特别容易踩的坑是很多人写“有效的括号”时会在遇到右括号时直接拿栈顶元素比较但忘了栈可能为空。比如输入是]你还没压入任何左括号直接stack[-1]就会报错。所以栈题里所有访问栈顶的操作第一件事永远是检查栈是否为空。“最长有效括号”稍微难一点它不只是判断配对还要记录长度。这时候栈里存的就不能是括号字符本身了而是下标。入栈的是(的下标遇到)时弹栈然后用当前位置减去新的栈顶位置就能算出长度。栈里存“索引而不是值”这个是栈题里经常出现的进阶思路后面单调栈还会用。2.2 单调栈模式找“下一个更大/更小”就锁定了它单调栈的识别特征非常鲜明题目要求你找“每个位置右边第一个更大/更小的元素”或者“左边第一个更小/更大的元素”。Hot 100 里的“每日温度”“下一个更大元素 I/II”“柱状图中最大的矩形”都是这类。先说“每日温度”题目给你每天的华氏温度要求返回一个数组每个位置表示“要等几天才能等到一个更高温”。暴力法是每个位置向后扫最坏 O(n²)。用单调栈怎么优化核心思路是维护一个从栈底到栈顶递减的栈里面存下标。每当新温度比栈顶温度高说明栈顶元素找到了“下一个更高温度”弹出它并计算结果然后继续比较新的栈顶否则把新温度压入栈。def dailyTemperatures(temperatures): n len(temperatures) ans [0] * n stack [] # 存下标栈底到栈顶对应的温度递减 for i, t in enumerate(temperatures): while stack and t temperatures[stack[-1]]: j stack.pop() ans[j] i - j stack.append(i) # 当前下标始终要入栈 return ans这里最关键的一点是为什么栈里存下标而不是温度值因为你要计算的答案是两个下标之间的距离只存温度的话弹出时你根本不知道位置在哪。这是一个常见教训写单调栈之前先问问自己“我最终要求的答案是什么它需要哪些信息”。“柱状图中最大的矩形”就更进阶一些它要找的是每个柱子“左右两侧第一个比它矮的柱子”这其实是个双向的单调栈问题。你可以在柱状图的两端各加一个高度为 0 的哨兵避免最后栈里还有元素没法处理。哨兵这个技巧在单调栈里非常实用后面第三部分是“遇到栈底残留怎么办”的标准解法。2.3 显式栈模拟递归/回溯把系统调用栈换成自己的Hot 100 里有几道跟树相关的题标准的递归写法很简单但面试官经常让你写迭代版本这就是在考“显式栈模拟递归”。比如二叉树的前序遍历递归版本是def preorder(root): if not root: return visit(root) preorder(root.left) preorder(root.right)系统栈帮你记住了“左子树遍历完要回来遍历右子树”这个现场。迭代版本要自己模拟这个栈帧def preorderTraversal(root): res [] stack [] cur root while cur or stack: while cur: res.append(cur.val) # 前序先访问 stack.append(cur) # 存右子树的现场 cur cur.left cur stack.pop().right # 回到现场 return res热词里提到的“backtrace栈回溯”在题目中往往是“路径”“组合”“排列”这一类问题比如 Hot 100 里的“组合总和”和“全排列”。回溯算法的本质就是深度优先搜索递归实现时回溯现场由系统栈保存如果你想显式控制搜索顺序、或者想避免递归过深就会手动用栈来模拟回溯过程。这种模式我给你的建议是先用递归把问题想清楚再考虑要不要改写成栈。递归版本的核心逻辑就是入栈和出栈的顺序。我见过不少面试者一上来就写栈版本结果 inorder 和 preorder 的压栈顺序搞混。先把递归版本跑通、理解每一帧里保存的信息是什么然后对照着写显式栈版本速度反而更快。2.4 表达式求值模式优先级与括号嵌套怎么处理Hot 100 里的“基本计算器”系列224、227 甚至 772 在会员里是栈题里很有区分度的一类。它们难在“怎么处理运算符优先级”和“怎么处理括号”。最简单的版本是 227 题“基本计算器 II”表达式只有 - * /没有括号。思路是遇到数字累加出完整的数。遇到把当前数直接入栈。遇到-把当前数的相反数入栈。遇到*把栈顶弹出来与当前数相乘后重新入栈。遇到/同理做整除。def calculate(s): stack [] num 0 sign # 初始运算符当作 for i, c in enumerate(s): if c.isdigit(): num num * 10 int(c) if (not c.isdigit() and c ! ) or i len(s) - 1: if sign : stack.append(num) elif sign -: stack.append(-num) elif sign *: stack[-1] stack[-1] * num elif sign /: stack[-1] int(stack[-1] / num) sign c num 0 return sum(stack)这个解法的巧妙之处在于通过把减法变成加负数、把乘除法在入栈前先算掉最后栈里只剩一批整数直接求和。整体思路是把“表达式的计算”转化为“一串数的累加”。等到 224 题“基本计算器”加上括号后就需要多一个栈用于保存括号外的符号状态。每遇到一个(把当前结果和符号压栈遇到)弹栈恢复外层状态。你会发现这种“遇到嵌套就想到栈”的思维跟 2.1 的括号配对是同一个底层逻辑。3. 从栈帧角度看算法栈栈不只是数据结构也是运行时机制热词里出现了“栈帧形成过程”“arm调用栈回溯”这些词看得出有人想把刷题栈跟底层运行机制打通。这条线其实很值得讲因为理解了系统栈很多算法题的行为你就能真正解释清楚。3.1 函数调用、递归深度与栈溢出每次函数调用系统会在调用栈上压入一个栈帧里面存了局部变量、参数、返回地址。递归函数特别消耗栈空间因为每一层递归都会建立新的栈帧。递归深度超过栈容量就是“栈溢出”。在嵌入式方向热词里那个 rp-2040 pico-sdk 增大栈空间 就是典型例子栈空间通常由链接脚本分配默认可能只有几 KB你如果写一个递归层数很深的算法或者申请了超大的局部数组很大概率程序跑飞或者 HardFault。这时候你需要主动调整栈大小或者在逻辑上避免深递归改成显式栈迭代。这个底层认知对刷题有什么用Leetcode 的递归题默认栈深度不够所以你不会遇到问题但真实项目里深度优先搜索如果递归深度到十万层级应用层就该崩了。如果你能在面试里主动提一句“这个递归层数可能很深我可以改成显式的栈迭代来避免栈溢出”是很加分的。3.2 栈变量与堆变量的生命周期差异热词里有“栈变量、全局静态变量”这里也顺带一提。C 语言里你在函数内部直接声明的局部变量默认是栈变量函数返回后这块内存自动失效全局静态变量则放在数据段生命周期是整个程序运行期。刷题时如果做“对象版本管理”或者说“Memento 模式”的实验你会更直观地体会到这种差异把“当前状态对象”压入栈就是保存一份快照出栈就是回退到上一个状态。这种撤销机制在编辑器、浏览器历史里到处都是跟前端路由返回、游戏回放都是同一个模型。3.3 ARM 调用栈回溯为什么重要热词里还有“arm调用栈回溯”简单说就是当程序崩溃时系统或者调试器通过遍历栈帧里的返回地址还原出“这个函数是谁调用的、一层层往上是谁”的调用链。你用 GDB 看 backtrace本质就是做这件事。而算法题里的“显式栈模拟回溯”你手动存的信息就是栈帧的自定义版本。这两个概念互通之后你再看“回溯”类题目会感觉很亲切你往栈里压入的每一个现场路径、中间状态、下一步计划本质上都是在手动做一次函数调用栈的“帧保存”。4. Hot 100 栈题逐题拆解三题带你吃透套路理论讲了这么多还是得上题。我挑三道有代表性的栈题完整走一遍分析过程第三道是很多人的分水岭建议仔细看。4.1 有效的括号从判断到最简实现题目给定只包含()[]{}的字符串判断括号是否有效。分析顺序是这样看到括号配对第一反应就是栈。遇到左括号入栈遇到右括号就检查栈顶是否是对应的左括号匹配则弹出不匹配直接失败。一个小技巧是用字典存配对表def isValid(s): stack [] pairs {): (, ]: [, }: {} for c in s: if c in pairs.values(): # 左括号 stack.append(c) elif c in pairs: # 右括号 if not stack or stack[-1] ! pairs[c]: return False stack.pop() else: return False return not stack我的经验是这道题给面试官的隐藏考点是“边界处理”输入为空字符串时应该返回 True。只有右括号时栈空访问要避免。只有左括号时最终栈不为空要判 False。嵌套层级很深时用栈不会爆递归才会这个点可以主动提。4.2 每日温度单调栈的完整推演前面已经给了代码这里补一个具体推演。假设temperatures [73, 74, 75, 71, 69, 72, 76, 73]i0, 73栈空压入0。i1, 7474 73弹出0ans[0]1压入1。i2, 7575 74弹出1ans[1]1压入2。i3, 7171 75压入3栈是[2,3]。i4, 6969 71压入4栈是[2,3,4]。i5, 7272 69弹出4ans[4]172 71弹出3ans[3]272 75压入5栈是[2,5]。i6, 7676 72弹出5ans[5]176 75弹出2ans[2]4压入6。i7, 7373 76压入7。最终答案是[1,1,4,2,1,1,0,0]。注意最后栈里的元素是[6,7]它们没有后续更高温度所以答案是 0。推演一遍你就能看出单调栈的四个关键点栈内存下标比较时用temperatures[stack[-1]]取值。出栈条件用while不是if因为新元素可能比栈里多个元素都大。每个元素入栈一次出栈最多一次所以总复杂度 O(n)。过程中遇到的“当前高度低于栈顶”时直接压栈它是将来某个元素的对齐项。4.3 基本计算器 II为什么最后栈里只剩“待求和”的数这道题是我觉得非常值得吃透的因为它是 224 题的跳板。核心工作分两步第一步是用一个栈把乘除法先算完第二步是对栈里剩下的数求和。逐步分析这个逻辑遇到空格直接跳过。遇到数字就累积num num * 10 digit注意字符可能连续比如12需要累加。遇到运算符或者走到字符串末尾时才用之前的sign处理num。这里的一个致命细节是sign记录的是“当前num前面的符号”而不是本次遍历到的符号。很多人在这一步绕晕了。举个例子 35 / 2 初始signnum0。i0字符3num3。i1字符因为不是数字触发处理sign所以stack.append(3)然后sign更新为当前字符实际上还是num0。i2字符5num5。i3字符空格跳过。i4字符/触发处理sign不对这里sign应该是在 i1 时被更新过一次也就是说在遇到/之前sign还是。所以处理时stack.append(5)然后sign/num0。i5字符2num2。走到末尾 i6 时触发处理此时sign/所以stack[-1] int(5 / 2) 2Python 的int(5/2)2。最后栈里是[3,2]求和得5。注意 Python 里负数整除的坑int(-3 / 2)得到-2还是-1int()在 Python 3 里是向零取整所以-3/2 -1.5int(-1.5) -1这正是 C 语言里的行为。如果用//则是向下取整-3//2 -2会导致算错。在写整除类型的计算器时建议用int(a / b)而不是a // b。再说一遍括号版本224是在这个基础上多加一层括号状态栈。当你遇到左括号时把当前累计结果和符号压栈在括号内重新开始一个“局部计算”右括号时先算完括号内的值再与栈里保存的外层结果合并。思想就是把一个大表达式切分成分层嵌套的小表达式栈负责记录这个切分路径。5. 刷题过程中的常见坑和调试技巧栈题代码通常很短但 bug 率高得惊人。我把常见的问题整理成一个速查表按出现频率排序。常见错误触发场景正确做法空栈访问只有右括号或多出了右半部分任何弹栈/看栈顶前先if not stack栈里存值而非索引每日温度、下一个更大元素答案需要位置差时必须存索引出栈条件用了if新元素可能连续淘汰多个栈顶用while直到栈顶不再满足条件表达式结束时忘记处理最后数字基本计算器循环结束后还要处理一次num单调栈哨兵丢了柱状图中最大矩形首尾加高度 0 的哨兵把整除写成//Python 计算器含负数用int(a / b)向零取整5.1 怎么用“打印栈”快速定位思路错在哪里我自己的习惯是写栈题时先不急着提交在关键位置打印栈的状态。比如写“下一个更大元素”的题每一步打一行i, value, stack肉眼看一下就能发现是出栈条件错了还是栈里存错东西了。举一个具体的排查例子。我之前写“柱状图中最大的矩形”时第一次版本没有加哨兵结果在结束之后栈里还有残留的柱子导致面积漏算。打印栈之后发现循环结束、栈不为空才想起要补哨兵。其实这个 bug 用逻辑推也能推出来但打印栈更快。5.2 一个容易忽略的复杂度细节很多人知道单调栈是 O(n)但没想过为什么。真正原因就是每个元素最多被压缩一次、被弹出一次。如果面试官追问“你真的每个元素只会出栈一次吗”你要能答上来。还有栈题的空间复杂度最坏情况下单调栈可能把所有元素都存进去比如温度递减时每个都比后一个高那就永远不触发弹出栈的大小可以达到 n。这种最坏情况的分析也是面试常问的别只说 O(n)要能举出什么时候会达到。5.3 递归深度和手动栈的取舍有些显式栈模拟递归的题写成手动栈之后代码会难看不少。我的实际经验是面试时先写递归版本答得对再谈优化。因为递归版本逻辑更贴近问题本身容易自证正确等面试官追问“如果递归太深会怎么样你能否给出迭代版本”这时候再切换到显式栈还能顺势展示你对栈帧的理解。当然热词里提到的“字符串解码”这类题你会看到用两个栈一个存数字一个存字符串处理括号层级的写法。这种题递归也能做但显式栈往往更直观调试也更方便这类题我建议直接练栈版本。6. 我的个人经验栈题怎么刷才能刷透最后聊点实在的。我在刷这部分题目时最大的体会是栈题难度不在编写而在“决策”。你写出来的代码通常十几行但你要想清楚四个问题栈里存什么什么时候入栈什么时候出栈出栈时做什么如果这四个问题回答得慢说明你还没有建立模式识别。我的建议是不要死记模板而是把每道题背后的“为什么存这个/为什么这个时候出栈”弄明白。拿“有效的括号”来说为什么左括号入栈右括号时弹栈因为右括号永远对应最近一个未匹配的左括号这个“最近未匹配”就是后进先出的定义。热词里面还有“全栈”这个词其实跟数据结构里的“栈”是个文字双关但底层思想是相通的。全栈开发讲究从输入到输出的完整链路栈题讲究从入栈到出栈的完整生命周期。理解“一条数据从进栈到出栈之间发生了什么”比背 100 道题都有用。我最后再分享一个小技巧刷完一道栈题之后试着把栈的每一步用文字写一遍就像我在 4.2 里那样推演。不要只在脑子里过写出来你会发现很多“好像懂了但其实不懂”的盲区。这个过程相当于手动做一次算法级别的栈帧回溯看得见每一步的栈内容你才真正把这个数据结构握在手里。
LeetCode栈题四大模式：配对消除、单调栈、模拟递归与表达式求值
刷 Leetcode Hot 100 的都知道栈这一块儿看着题目不多但几乎每道题都能牵扯出好几个面试官爱问的考点括号匹配、单调栈、表达式求值、用显式栈模拟递归……标题里写个“栈”字翻译过来其实是“一类用后进先出思想解决特定子问题的套路合集”。这篇东西我打算直接按刷题实战的角度拆开讲不只是把题解列一遍更重要的是把“为什么这道题要用栈”“栈里到底存什么”“边界条件怎么抠”这几个核心问题说清楚。适合谁看两种人一种是刚开始刷 Hot 100碰到栈题总是一看就会、一写就废的另一种是栈题刷过几遍但碰到“基本计算器”这种中等偏上的题还是发怵的。我会用大量实际代码和逐步推演尽量让你看完能直接上手复现。栈这个东西本质上就是在帮你记住“之前发生的事”所有的题目变体都绕不开这个内核。1. 为什么栈在 Hot 100 里这么重要——先搞懂它到底在解决什么问题很多人把栈理解成“一种只能从顶部操作的数据结构”这没错但太表面了。你真正应该记住的是栈解决的是“需要回溯、需要记住最近状态、需要按嵌套顺序处理”的一类问题。Leetcode Hot 100 里凡是能用栈解的题几乎都满足这个描述。1.1 栈的抽象模型后进先出到底意味着什么拿日常生活中的叠盘子来类比你往桌上一张一张叠盘子最后放上去的盘子永远是第一个被拿走的。这个“后进先出”的特性决定了栈天然适合处理具有嵌套结构、对称结构、或者需要逆序处理的数据。在算法题里这个模型有几个具体的表现形式配对消除比如括号、HTML标签、路径里的..遇到配对的就消除栈天然是“记录左边、遇到右边就检查”的容器。最近相关性比如“下一个更大元素、每日温度”你要找的是“当前元素右边第一个比它大的”这要求你记住已经遍历过但还没处理完的元素而且越是“最近”的元素越先被处理。显式记忆现场递归函数本身用的是系统调用栈当你想把递归改成迭代、或者控制递归的深度和方向时你手动维护一个栈就能模拟系统栈的行为。表达式求值括号的嵌套、运算符的优先级本质上是两三种不同“上下文”的切换栈能在不同层级之间来回跳。热词里提到的“backtrace栈回溯”和“栈帧形成过程”其实就是从系统层面印证了这套思想程序运行时每次函数调用都会在调用栈上压入一个栈帧函数返回时栈帧弹出整个调用链就是一棵回溯树。你刷题用的栈跟系统调用栈是同构的只是你把这个机制显式地拿出来了。1.2 Hot 100 中栈题目的分布与共性Hot 100 里直接标注“栈”标签的题大概二十多道但实际用栈作为最优解的题还包括一些容易忽略的比如“反转链表”可以用栈实现、“二叉树的中序遍历”显式栈版本。我做了一个粗略归类题型归类典型题目栈的角色括号与配对消除有效的括号、最长有效括号记录左括号位置延迟匹配单调栈每日温度、下一个更大元素、柱状图中最大的矩形维护一个有序的候选集表达式求值基本计算器、逆波兰表达式求值保存数字和运算符处理优先级显式栈模拟递归/回溯二叉树遍历、字符串解码、迭代法求子树替代系统调用栈栈与队列互转用栈实现队列、用队列实现栈用两个栈倒腾顺序共性很明显凡是栈题解题的关键一定不是“你会不会用栈”而是“你决定栈里存什么、什么时候入栈、什么时候出栈、出栈时做什么”。这四个问题想清楚了代码只是顺手的事。1.3 为什么“单调栈”能比暴力快这么多Hot 100 里有好几道单调栈的题很多人初看时觉得没必要搞懂暴力双循环也能过为什么还要维护一个单调栈答案是时间复杂度从 O(n²) 降到 O(n)。打个比方暴力法相当于你每次站在一个位置问“我右边有没有比我高的”每次都往后扫一遍单调栈则相当于你手里拿着一张“待解决名单”每当新元素进来就把名单里那些已经被解答的人划掉。每个人最多入栈一次、出栈一次所以总时间是线性的。这个思想在很多非栈题里也会出现比如滑动窗口最大值、接雨水Hot 100 里接雨水的双指针/单调栈解法都值得研究。所以我会说单调栈是你在 Hot 100 栈题里最值得花时间啃透的一个点。2. 栈类题目的四种核心模式以及怎么一眼识别刷题刷多了你会发现栈题基本就是四个套路。看清题目长什么样就能立刻知道该用哪个套路这是提高效率的关键。2.1 配对消除模式遇到“对称结构”先想到栈这种模式的特点是输入是一串有配对规则的元素你需要处理嵌套或前后关联。最典型的就是括号。识别特征也很简单题目出现了()[]{}、成对的begin/end、或者是“消除相邻重复项”这类词。核心写法模板def helper(s): stack [] for c in s: if c 是左半部分: stack.append(c) else: # 这里是一个关键点先判空 if not stack or stack[-1] ! 匹配的右半部分: return False stack.pop() return not stack # 结束之后栈必须为空一个特别容易踩的坑是很多人写“有效的括号”时会在遇到右括号时直接拿栈顶元素比较但忘了栈可能为空。比如输入是]你还没压入任何左括号直接stack[-1]就会报错。所以栈题里所有访问栈顶的操作第一件事永远是检查栈是否为空。“最长有效括号”稍微难一点它不只是判断配对还要记录长度。这时候栈里存的就不能是括号字符本身了而是下标。入栈的是(的下标遇到)时弹栈然后用当前位置减去新的栈顶位置就能算出长度。栈里存“索引而不是值”这个是栈题里经常出现的进阶思路后面单调栈还会用。2.2 单调栈模式找“下一个更大/更小”就锁定了它单调栈的识别特征非常鲜明题目要求你找“每个位置右边第一个更大/更小的元素”或者“左边第一个更小/更大的元素”。Hot 100 里的“每日温度”“下一个更大元素 I/II”“柱状图中最大的矩形”都是这类。先说“每日温度”题目给你每天的华氏温度要求返回一个数组每个位置表示“要等几天才能等到一个更高温”。暴力法是每个位置向后扫最坏 O(n²)。用单调栈怎么优化核心思路是维护一个从栈底到栈顶递减的栈里面存下标。每当新温度比栈顶温度高说明栈顶元素找到了“下一个更高温度”弹出它并计算结果然后继续比较新的栈顶否则把新温度压入栈。def dailyTemperatures(temperatures): n len(temperatures) ans [0] * n stack [] # 存下标栈底到栈顶对应的温度递减 for i, t in enumerate(temperatures): while stack and t temperatures[stack[-1]]: j stack.pop() ans[j] i - j stack.append(i) # 当前下标始终要入栈 return ans这里最关键的一点是为什么栈里存下标而不是温度值因为你要计算的答案是两个下标之间的距离只存温度的话弹出时你根本不知道位置在哪。这是一个常见教训写单调栈之前先问问自己“我最终要求的答案是什么它需要哪些信息”。“柱状图中最大的矩形”就更进阶一些它要找的是每个柱子“左右两侧第一个比它矮的柱子”这其实是个双向的单调栈问题。你可以在柱状图的两端各加一个高度为 0 的哨兵避免最后栈里还有元素没法处理。哨兵这个技巧在单调栈里非常实用后面第三部分是“遇到栈底残留怎么办”的标准解法。2.3 显式栈模拟递归/回溯把系统调用栈换成自己的Hot 100 里有几道跟树相关的题标准的递归写法很简单但面试官经常让你写迭代版本这就是在考“显式栈模拟递归”。比如二叉树的前序遍历递归版本是def preorder(root): if not root: return visit(root) preorder(root.left) preorder(root.right)系统栈帮你记住了“左子树遍历完要回来遍历右子树”这个现场。迭代版本要自己模拟这个栈帧def preorderTraversal(root): res [] stack [] cur root while cur or stack: while cur: res.append(cur.val) # 前序先访问 stack.append(cur) # 存右子树的现场 cur cur.left cur stack.pop().right # 回到现场 return res热词里提到的“backtrace栈回溯”在题目中往往是“路径”“组合”“排列”这一类问题比如 Hot 100 里的“组合总和”和“全排列”。回溯算法的本质就是深度优先搜索递归实现时回溯现场由系统栈保存如果你想显式控制搜索顺序、或者想避免递归过深就会手动用栈来模拟回溯过程。这种模式我给你的建议是先用递归把问题想清楚再考虑要不要改写成栈。递归版本的核心逻辑就是入栈和出栈的顺序。我见过不少面试者一上来就写栈版本结果 inorder 和 preorder 的压栈顺序搞混。先把递归版本跑通、理解每一帧里保存的信息是什么然后对照着写显式栈版本速度反而更快。2.4 表达式求值模式优先级与括号嵌套怎么处理Hot 100 里的“基本计算器”系列224、227 甚至 772 在会员里是栈题里很有区分度的一类。它们难在“怎么处理运算符优先级”和“怎么处理括号”。最简单的版本是 227 题“基本计算器 II”表达式只有 - * /没有括号。思路是遇到数字累加出完整的数。遇到把当前数直接入栈。遇到-把当前数的相反数入栈。遇到*把栈顶弹出来与当前数相乘后重新入栈。遇到/同理做整除。def calculate(s): stack [] num 0 sign # 初始运算符当作 for i, c in enumerate(s): if c.isdigit(): num num * 10 int(c) if (not c.isdigit() and c ! ) or i len(s) - 1: if sign : stack.append(num) elif sign -: stack.append(-num) elif sign *: stack[-1] stack[-1] * num elif sign /: stack[-1] int(stack[-1] / num) sign c num 0 return sum(stack)这个解法的巧妙之处在于通过把减法变成加负数、把乘除法在入栈前先算掉最后栈里只剩一批整数直接求和。整体思路是把“表达式的计算”转化为“一串数的累加”。等到 224 题“基本计算器”加上括号后就需要多一个栈用于保存括号外的符号状态。每遇到一个(把当前结果和符号压栈遇到)弹栈恢复外层状态。你会发现这种“遇到嵌套就想到栈”的思维跟 2.1 的括号配对是同一个底层逻辑。3. 从栈帧角度看算法栈栈不只是数据结构也是运行时机制热词里出现了“栈帧形成过程”“arm调用栈回溯”这些词看得出有人想把刷题栈跟底层运行机制打通。这条线其实很值得讲因为理解了系统栈很多算法题的行为你就能真正解释清楚。3.1 函数调用、递归深度与栈溢出每次函数调用系统会在调用栈上压入一个栈帧里面存了局部变量、参数、返回地址。递归函数特别消耗栈空间因为每一层递归都会建立新的栈帧。递归深度超过栈容量就是“栈溢出”。在嵌入式方向热词里那个 rp-2040 pico-sdk 增大栈空间 就是典型例子栈空间通常由链接脚本分配默认可能只有几 KB你如果写一个递归层数很深的算法或者申请了超大的局部数组很大概率程序跑飞或者 HardFault。这时候你需要主动调整栈大小或者在逻辑上避免深递归改成显式栈迭代。这个底层认知对刷题有什么用Leetcode 的递归题默认栈深度不够所以你不会遇到问题但真实项目里深度优先搜索如果递归深度到十万层级应用层就该崩了。如果你能在面试里主动提一句“这个递归层数可能很深我可以改成显式的栈迭代来避免栈溢出”是很加分的。3.2 栈变量与堆变量的生命周期差异热词里有“栈变量、全局静态变量”这里也顺带一提。C 语言里你在函数内部直接声明的局部变量默认是栈变量函数返回后这块内存自动失效全局静态变量则放在数据段生命周期是整个程序运行期。刷题时如果做“对象版本管理”或者说“Memento 模式”的实验你会更直观地体会到这种差异把“当前状态对象”压入栈就是保存一份快照出栈就是回退到上一个状态。这种撤销机制在编辑器、浏览器历史里到处都是跟前端路由返回、游戏回放都是同一个模型。3.3 ARM 调用栈回溯为什么重要热词里还有“arm调用栈回溯”简单说就是当程序崩溃时系统或者调试器通过遍历栈帧里的返回地址还原出“这个函数是谁调用的、一层层往上是谁”的调用链。你用 GDB 看 backtrace本质就是做这件事。而算法题里的“显式栈模拟回溯”你手动存的信息就是栈帧的自定义版本。这两个概念互通之后你再看“回溯”类题目会感觉很亲切你往栈里压入的每一个现场路径、中间状态、下一步计划本质上都是在手动做一次函数调用栈的“帧保存”。4. Hot 100 栈题逐题拆解三题带你吃透套路理论讲了这么多还是得上题。我挑三道有代表性的栈题完整走一遍分析过程第三道是很多人的分水岭建议仔细看。4.1 有效的括号从判断到最简实现题目给定只包含()[]{}的字符串判断括号是否有效。分析顺序是这样看到括号配对第一反应就是栈。遇到左括号入栈遇到右括号就检查栈顶是否是对应的左括号匹配则弹出不匹配直接失败。一个小技巧是用字典存配对表def isValid(s): stack [] pairs {): (, ]: [, }: {} for c in s: if c in pairs.values(): # 左括号 stack.append(c) elif c in pairs: # 右括号 if not stack or stack[-1] ! pairs[c]: return False stack.pop() else: return False return not stack我的经验是这道题给面试官的隐藏考点是“边界处理”输入为空字符串时应该返回 True。只有右括号时栈空访问要避免。只有左括号时最终栈不为空要判 False。嵌套层级很深时用栈不会爆递归才会这个点可以主动提。4.2 每日温度单调栈的完整推演前面已经给了代码这里补一个具体推演。假设temperatures [73, 74, 75, 71, 69, 72, 76, 73]i0, 73栈空压入0。i1, 7474 73弹出0ans[0]1压入1。i2, 7575 74弹出1ans[1]1压入2。i3, 7171 75压入3栈是[2,3]。i4, 6969 71压入4栈是[2,3,4]。i5, 7272 69弹出4ans[4]172 71弹出3ans[3]272 75压入5栈是[2,5]。i6, 7676 72弹出5ans[5]176 75弹出2ans[2]4压入6。i7, 7373 76压入7。最终答案是[1,1,4,2,1,1,0,0]。注意最后栈里的元素是[6,7]它们没有后续更高温度所以答案是 0。推演一遍你就能看出单调栈的四个关键点栈内存下标比较时用temperatures[stack[-1]]取值。出栈条件用while不是if因为新元素可能比栈里多个元素都大。每个元素入栈一次出栈最多一次所以总复杂度 O(n)。过程中遇到的“当前高度低于栈顶”时直接压栈它是将来某个元素的对齐项。4.3 基本计算器 II为什么最后栈里只剩“待求和”的数这道题是我觉得非常值得吃透的因为它是 224 题的跳板。核心工作分两步第一步是用一个栈把乘除法先算完第二步是对栈里剩下的数求和。逐步分析这个逻辑遇到空格直接跳过。遇到数字就累积num num * 10 digit注意字符可能连续比如12需要累加。遇到运算符或者走到字符串末尾时才用之前的sign处理num。这里的一个致命细节是sign记录的是“当前num前面的符号”而不是本次遍历到的符号。很多人在这一步绕晕了。举个例子 35 / 2 初始signnum0。i0字符3num3。i1字符因为不是数字触发处理sign所以stack.append(3)然后sign更新为当前字符实际上还是num0。i2字符5num5。i3字符空格跳过。i4字符/触发处理sign不对这里sign应该是在 i1 时被更新过一次也就是说在遇到/之前sign还是。所以处理时stack.append(5)然后sign/num0。i5字符2num2。走到末尾 i6 时触发处理此时sign/所以stack[-1] int(5 / 2) 2Python 的int(5/2)2。最后栈里是[3,2]求和得5。注意 Python 里负数整除的坑int(-3 / 2)得到-2还是-1int()在 Python 3 里是向零取整所以-3/2 -1.5int(-1.5) -1这正是 C 语言里的行为。如果用//则是向下取整-3//2 -2会导致算错。在写整除类型的计算器时建议用int(a / b)而不是a // b。再说一遍括号版本224是在这个基础上多加一层括号状态栈。当你遇到左括号时把当前累计结果和符号压栈在括号内重新开始一个“局部计算”右括号时先算完括号内的值再与栈里保存的外层结果合并。思想就是把一个大表达式切分成分层嵌套的小表达式栈负责记录这个切分路径。5. 刷题过程中的常见坑和调试技巧栈题代码通常很短但 bug 率高得惊人。我把常见的问题整理成一个速查表按出现频率排序。常见错误触发场景正确做法空栈访问只有右括号或多出了右半部分任何弹栈/看栈顶前先if not stack栈里存值而非索引每日温度、下一个更大元素答案需要位置差时必须存索引出栈条件用了if新元素可能连续淘汰多个栈顶用while直到栈顶不再满足条件表达式结束时忘记处理最后数字基本计算器循环结束后还要处理一次num单调栈哨兵丢了柱状图中最大矩形首尾加高度 0 的哨兵把整除写成//Python 计算器含负数用int(a / b)向零取整5.1 怎么用“打印栈”快速定位思路错在哪里我自己的习惯是写栈题时先不急着提交在关键位置打印栈的状态。比如写“下一个更大元素”的题每一步打一行i, value, stack肉眼看一下就能发现是出栈条件错了还是栈里存错东西了。举一个具体的排查例子。我之前写“柱状图中最大的矩形”时第一次版本没有加哨兵结果在结束之后栈里还有残留的柱子导致面积漏算。打印栈之后发现循环结束、栈不为空才想起要补哨兵。其实这个 bug 用逻辑推也能推出来但打印栈更快。5.2 一个容易忽略的复杂度细节很多人知道单调栈是 O(n)但没想过为什么。真正原因就是每个元素最多被压缩一次、被弹出一次。如果面试官追问“你真的每个元素只会出栈一次吗”你要能答上来。还有栈题的空间复杂度最坏情况下单调栈可能把所有元素都存进去比如温度递减时每个都比后一个高那就永远不触发弹出栈的大小可以达到 n。这种最坏情况的分析也是面试常问的别只说 O(n)要能举出什么时候会达到。5.3 递归深度和手动栈的取舍有些显式栈模拟递归的题写成手动栈之后代码会难看不少。我的实际经验是面试时先写递归版本答得对再谈优化。因为递归版本逻辑更贴近问题本身容易自证正确等面试官追问“如果递归太深会怎么样你能否给出迭代版本”这时候再切换到显式栈还能顺势展示你对栈帧的理解。当然热词里提到的“字符串解码”这类题你会看到用两个栈一个存数字一个存字符串处理括号层级的写法。这种题递归也能做但显式栈往往更直观调试也更方便这类题我建议直接练栈版本。6. 我的个人经验栈题怎么刷才能刷透最后聊点实在的。我在刷这部分题目时最大的体会是栈题难度不在编写而在“决策”。你写出来的代码通常十几行但你要想清楚四个问题栈里存什么什么时候入栈什么时候出栈出栈时做什么如果这四个问题回答得慢说明你还没有建立模式识别。我的建议是不要死记模板而是把每道题背后的“为什么存这个/为什么这个时候出栈”弄明白。拿“有效的括号”来说为什么左括号入栈右括号时弹栈因为右括号永远对应最近一个未匹配的左括号这个“最近未匹配”就是后进先出的定义。热词里面还有“全栈”这个词其实跟数据结构里的“栈”是个文字双关但底层思想是相通的。全栈开发讲究从输入到输出的完整链路栈题讲究从入栈到出栈的完整生命周期。理解“一条数据从进栈到出栈之间发生了什么”比背 100 道题都有用。我最后再分享一个小技巧刷完一道栈题之后试着把栈的每一步用文字写一遍就像我在 4.2 里那样推演。不要只在脑子里过写出来你会发现很多“好像懂了但其实不懂”的盲区。这个过程相当于手动做一次算法级别的栈帧回溯看得见每一步的栈内容你才真正把这个数据结构握在手里。
