最近把 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。遍历到1，1 > nums[0]=2不成立，不弹栈，入栈索引1。此时栈底到栈顶为[0, 1]，对应值[2, 1]，满足递减。遍历到3，3 > nums[1]=1，弹出索引1，res[1] = 3；继续比较，3 > nums[0]=2，弹出索引0，res[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 就沙盘演算一遍。拿单调栈画两个简单的数组迭代过程，你会很快理解“下一个更大元素”里为什么栈会保持递减、为什么新大元素一到位就会连环弹出。画三遍之后，脑子里的栈模型就建立起来了，以后再遇到栈设计题、表达式求值题，你甚至能从纸上“看到”代码该怎么跑了。刷完这批栈题，我自己最大的体会是：栈的题目并不难，难的是识别出“这里要用栈”。一旦识别出来，解法框架其实都是高度相似的——要么是括号配对，要么是单调栈维护，要么是模拟递归或表达式运算。最后再分享一个小技巧：做栈题前先别急着写代码，先在纸上演算一遍标准流程，把中间过程和栈的状态写清楚，再开始敲代码，你会发现代码几乎一次通过，调试时间至少省一半。
最近把 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。遍历到1，1 > nums[0]=2不成立，不弹栈，入栈索引1。此时栈底到栈顶为[0, 1]，对应值[2, 1]，满足递减。遍历到3，3 > nums[1]=1，弹出索引1，res[1] = 3；继续比较，3 > nums[0]=2，弹出索引0，res[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 就沙盘演算一遍。拿单调栈画两个简单的数组迭代过程，你会很快理解“下一个更大元素”里为什么栈会保持递减、为什么新大元素一到位就会连环弹出。画三遍之后，脑子里的栈模型就建立起来了，以后再遇到栈设计题、表达式求值题，你甚至能从纸上“看到”代码该怎么跑了。刷完这批栈题，我自己最大的体会是：栈的题目并不难，难的是识别出“这里要用栈”。一旦识别出来，解法框架其实都是高度相似的——要么是括号配对，要么是单调栈维护，要么是模拟递归或表达式运算。最后再分享一个小技巧：做栈题前先别急着写代码，先在纸上演算一遍标准流程，把中间过程和栈的状态写清楚，再开始敲代码，你会发现代码几乎一次通过，调试时间至少省一半。