刷了不少题之后你会发现一个规律栈Stack这个东西看起来是最不起眼的基础数据结构但在实际刷题和面试里的出镜率高得吓人。而且它有个特点——直接考栈操作的题很少真正难的是你根本没想到这题能用栈。LeetCode栈类题目的常见题型其实非常集中套路翻来覆去就那么几套配对消除、单调性维护、递归转迭代、嵌套状态恢复。把这些套路吃透栈相关的中等题基本都能在五分钟内锁定思路。这篇文章我就按题型把栈的常见考法梳理一遍每类都给模板代码和边界坑适合从初级刷到进阶的同学参考。1. 为什么刷栈题要先建立栈感1.1 栈的本质决定了它的三个应用方向栈的核心特性只有一句话后进先出LIFO。但这个特性在不同场景下演化出三种完全不同的用法很多人刷题时觉得栈难是因为把三种用法混为一谈。第一种用法是暂存现场。当我们需要处理嵌套结构、需要记住之前的某个状态以便后面恢复时栈就是天然的草稿纸。比如括号匹配、HTML标签闭合、函数调用栈本质都是遇到一个开始标记压栈记住遇到结束标记弹栈核对。第二种用法是维护单调性。栈内的元素保持严格的递增或递减关系利用这种单调性可以在O(n)时间内解决找下一个更大/更小元素的问题。第三种用法是模拟递归过程。递归在计算机里本来就是靠系统栈实现的当我们把递归改成迭代时就在代码里显式地开一个栈来模拟系统行为二叉树遍历是典型代表。理解这三种方向之后后面所有栈题都能对号入座。1.2 快速判断一道题能否用栈的四条特征实战中判断一道题该不该用栈我总结了四条经验命中任意一条就值得往栈的方向想题目里出现了**相邻元素之间的某种抵消、匹配、比较**关系尤其是连续性的相邻关系。数据存在嵌套结构比如括号套括号、多层路径、重复组合。处理过程需要回退到最近的上一个状态也就是后悔药逻辑。题目暴力解需要反复从后往前看比如每个元素向右找第一个大于它的数。反过来如果题目涉及先进先出、排队轮流处理那应该想队列而不是栈如果只是单纯地找全局最大最小那是排序或堆的事。栈题的关键不在用栈模拟流程而在识别出这是一个需要反向回溯或局部比较的问题。2. 配对消除类栈的消消乐玩法2.1 有效括号与删除相邻重复项同一个模板配对消除是栈最直观的应用。LeetCode第20题有效的括号就是最经典的入门题。它的核心逻辑是左括号入栈右括号出栈并检查是否匹配。任何不匹配或栈空的情况直接返回false。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这里最容易被忽略的是结尾的return not stack。我见过不少人只检查了中间匹配过程忘了最后还要确认栈被清空结果遇到(((这种输入就出错了。栈非空说明有左括号没被匹配字符串无效。第1047题删除字符串中的所有相邻重复项看起来跟括号无关但思路一模一样遍历字符串当前字符和栈顶相同就弹出不同就压入。这就是消消乐的变体——只不过括号题消的是配对的左右括号这题消的是相邻重复字符。def removeDuplicates(s: str) - str: stack [] for ch in s: if stack and stack[-1] ch: stack.pop() else: stack.append(ch) return .join(stack)这道题容易踩的坑是消除之后产生的新相邻重复。比如abbaca这种删掉中间的bb后a和a又相邻了。如果不用栈、直接暴力删字符串还得从头重新扫描。栈的做法天然处理了这种情况——每次只和栈顶比较栈顶就是当前最后一个没被消除的字符删除后新的栈顶自然就是前一个未配对元素不需要回溯扫描。2.2 表达式求值配对消除思想的延伸表达式求值是配对消除的进阶版。第150题逆波兰表达式求值后缀表达式用的是操作数栈遇到数字就压栈遇到运算符就弹出两个操作数计算结果再压回去。def evalRPN(tokens: list[str]) - int: stack [] for t in tokens: if t not in -*/: stack.append(int(t)) else: 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: stack.append(int(a / b)) return stack[-1]两个容易出错的点必须提醒。第一减法除法要注意操作数顺序先弹出的是右操作数b后弹出的是左操作数a写反了结果全错。第二Python的a / b在负数除法时结果可能与预期不符直接用int(a / b)先除后取整比用//更稳妥因为//是向下取整遇到负数是往负无穷方向取整的。更复杂的表达式求值中缀转后缀、带括号的四则运算本质也是两套栈的配合一个操作数栈、一个运算符栈。运算符入栈前先弹出所有优先级不低于它的运算符遇到左括号直接入栈遇到右括号一直弹到左括号。理解了配对消除这个底层逻辑这些变化就都通了。3. 单调栈栈题里含金量最高的一类3.1 下一个更大元素单调栈的入门模板阵单调栈是栈类题目里最值得花时间啃的一块因为它在中等题里的出现频率实在太高。先拿第496题下一个更大元素和第739题每日温度开刀。第739题这样描述给你每天的温度列表返回一个数组每个位置表示要等多少天才能等到更高的温度。def dailyTemperatures(T: list[int]) - list[int]: n len(T) ans [0] * n stack [] for i in range(n): while stack and T[i] T[stack[-1]]: prev stack.pop() ans[prev] i - prev stack.append(i) return ans这个模板的要点是栈里存的是下标不是值。为什么存下标因为我们要算距离天数只有通过下标相减才能得到。栈内元素维持从栈底到栈顶递减的结构也就是所谓的单调递减栈——遇到一个更大的新元素时把栈里所有比它小的旧元素全部弹出同时记录答案。单调性为什么高效因为栈里的元素都是还没找到下一个更大值的候选者。一旦来了更大的值这些候选者统一算账出栈每个元素最多入栈一次、出栈一次整体O(n)。比暴力解法每个元素都要往后扫描O(n^2)快了一个数量级。3.2 柱状图中最大的矩形单调栈的灵魂题第84题柱状图中最大的矩形是单调栈的分水岭。做过这题和没做过这题的面试表现完全两样。给定一组柱子高度找最大矩形面积。核心思路每个柱子作为矩形高度时向左向右扩展到第一个比它矮的柱子就能算出以它为高的最大宽度。用单调栈维护柱子下标保持栈内高度递增从栈底到栈顶。当遇到比自己矮的柱子时说明栈顶柱子右侧边界确定可以结算面积。def largestRectangleArea(heights: list[int]) - int: heights [0] heights [0] stack [] max_area 0 for i in range(len(heights)): while stack and heights[i] heights[stack[-1]]: h heights[stack.pop()] w i - stack[-1] - 1 max_area max(max_area, h * w) stack.append(i) return max_area这里的两个哨兵0是整个解法的灵魂。开头加0保证栈不为空结尾加0保证所有柱子最后都能被弹出结算。如果不加末尾的0最后栈里还会残留一些递增的柱子没计算面积代码会复杂很多。我第一次做这题时踩过一个具体坑结算宽度时w i - stack[-1] - 1这里用的是弹出之后新栈顶的下标。我一开始写成了i - h_index以为宽度是当前柱子和被弹出柱子的距离实际上完全错了。弹出之后再往左看到新栈顶为止才是这个高度的有效宽度范围。3.3 接雨水把单调栈用到极致第42题接雨水是单调栈的集大成者也是面试高频题。暴力解法是每个位置找左右最大高度的较小值减去当前高度累加。单调栈的解法思路是栈内维护递减高度下标当遇到较高的柱子时把栈顶弹出作为坑底此时左右两侧较高的柱子栈内新栈顶和当前柱子形成了U形就能结算这一个坑能接的水量。def trap(height: list[int]) - int: stack [] ans 0 for i, h in enumerate(height): while stack and h height[stack[-1]]: bottom height[stack.pop()] if not stack: break left stack[-1] limited min(height[left], h) - bottom ans limited * (i - left - 1) stack.append(i) return ans这个写法是按层结算水的每次弹出一个坑底计算的是这个高度区间的一小条水量。一定要注意弹出后栈为空的情况说明左侧没有更高的墙了水存不住直接break。接雨水还有双指针和动态规划两种解法单调栈不是空间最优的O(n)空间但它是三种解法中最不容易出错、最容易讲清楚思路的。面试时如果时间紧优先写单调栈版思路顺不容易翻车。我在实际面试模拟中发现能五分钟内写对单调栈版接雨水的人对栈的理解基本到位了。4. 栈与树的组合拳迭代遍历与BST迭代器4.1 为什么递归遍历要改成栈的迭代写法二叉树的前中后序遍历教科书先教递归。但很多面试题要求能否用迭代实现或者题目本身限制了递归深度。递归的底层就是系统栈在维护调用现场我们显式用一个栈来模拟本质上没有换算法只是把隐式的栈变成了显式的栈。前序遍历的迭代写法非常简洁根节点入栈弹出处理先压右孩子再压左孩子。def preorderTraversal(root): if not root: return [] stack [root] res [] while stack: node stack.pop() res.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return res先压右再压左因为栈是LIFO右子树后进会在左子树之后才处理到这正好符合根-左-右的前序顺序。这个细节我见过很多人写反写反就变成先处理右子树了。中序遍历的迭代要稍微绕一点一路往左走并压栈走到空就弹出处理然后转向右子树。def inorderTraversal(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这个一直往左压压到空再回头的模式就是中序遍历的本质。理解这个之后很多需要按中序顺序访问BST节点的题就有基础了。4.2 二叉搜索树迭代器把中序遍历拆成手动版第173题二叉搜索树迭代器要求实现next()和hasNext()每次调用返回BST中序遍历的下一个值。如果直接用数组保存中序结果再依次返回空间是O(n)。面试官通常会追问能不能做到均摊O(h)空间h为树高。其实做法就是把上面的中序遍历拆开初始化时把根到最左端的所有节点压栈next()弹出栈顶并处理其右子树的最左链。class BSTIterator: def __init__(self, root): self.stack [] self._push_left(root) def _push_left(self, node): while node: self.stack.append(node) node node.left def next(self): node self.stack.pop() self._push_left(node.right) return node.val def hasNext(self): return bool(self.stack)这里每次_push_left往栈里推的节点平均下来是O(1)个所以均摊O(h)空间是完全成立的。做这道题最大的收获不是背代码而是理解了递归展开的本质递归到哪里栈的状态就是哪里手动维护栈就等于接管了系统的调用现场。5. 嵌套与回溯类栈的状态恢复进阶玩法5.1 括号生成与回溯把压栈出栈的思想抽象化第22题括号生成让生成n对括号的所有合法组合。这题表面不直接使用栈数据结构但它的核心思想和栈完全一致记录当前左右括号的已用数量通过递归回溯枚举所有可能。回溯本身就是在维护一个状态栈递归进入时是压栈回溯出来是弹栈。def generateParenthesis(n: int) - list[str]: ans [] def backtrack(s, left, right): if len(s) 2 * n: ans.append(s) return if left n: backtrack(s (, left 1, right) if right left: backtrack(s ), left, right 1) backtrack(, 0, 0) return ans这里的剪枝条件right left是核心只要右括号数量小于左括号就可以加右括号如果右括号数量等于左括号加右括号就会产生非法的单独右括号。理解了括号匹配的栈逻辑这个剪枝条件就非常自然了——栈里左括号没被配平之前右括号永远不能超量出现。5.2 解码字符串与简化路径栈处理嵌套状态的典型第394题解码字符串是嵌套恢复类的代表。题目类似3[a2[c]]要解码成accaccacc。难点在嵌套外层的3要作用于内层解码出的字符串。这时候需要两个栈或者一个元组栈数字栈保存重复次数字符串栈保存括号前的已拼接结果。def decodeString(s: str) - str: stack [] for ch in s: if ch ]: tmp [] while stack and stack[-1] ! [: tmp.append(stack.pop()) stack.pop() # 弹出 [ num [] while stack and stack[-1].isdigit(): num.append(stack.pop()) n int(.join(reversed(num))) stack.append(.join(reversed(tmp)) * n) else: stack.append(ch) return .join(stack)这里我吃过一个亏把tmp里的字符弹出后直接reversed(tmp)再拼接但因为弹出顺序是从栈顶往栈底tmp里存的是逆序必须反转回来。如果直接用.join(tmp)会得到完全反过来的字符串。这种弹出顺序天然逆序的坑在栈题里反复出现养成习惯出栈后需要恢复原顺序时第一个动作就是反转。第71题简化路径则是用栈处理路径组件按/切分后遇到普通组件入栈遇到..弹出栈顶组件表示返回上一级遇到.或空字符串忽略。def simplifyPath(path: str) - str: stack [] for part in path.split(/): if part in (, .): continue if part ..: if stack: stack.pop() else: stack.append(part) return / /.join(stack)这道题最容易踩的坑是..之后栈为空的情况。比如路径/../按理说..已经在根目录没法再往上了应该忽略而不是报错。代码里if stack的判断就处理了这个边界。另一个坑是路径末尾的/会split出空字符串必须过滤。这些都体现了栈题的一个共同规律边界条件的判断顺序往往决定了代码能不能一次通过。6. 刷了三年栈题我认为最值得记住的坑与经验6.1 栈题最容易翻车的五个细节第一个是空栈操作。任何stack.pop()或stack[-1]前都要确认栈非空尤其是配对类和结算类的题目。括号匹配题里多了一个多余的右括号单调栈里高处遇到更矮的柱子都可能让栈提前空掉。第二个是栈里存什么。存下标还是存值决定了你能不能在O(1)时间内拿到位置信息。计算距离、宽度时一定要存下标这是每日温度和柱状图最大矩形涨过的教训。第三个是出栈顺序是逆序的。只要从栈里弹出一串元素它们的顺序一定是反的。要在意原顺序时记得反转解码字符串那题就是典型。第四个是哨兵元素。在数组两端放一个边界守卫0或极大值可以避免大量边界判断。柱状图标题在头和尾各加一个0接雨水也可以用类似技巧简化逻辑。用哨兵不是耍小聪明而是真的能减少bug。第五个是复杂度不是假象。单调栈的O(n)是每个元素最多入栈一次出栈一次的均摊结果。写代码时确认这个性质没有被破坏比如嵌套循环里有没有可能在极端情况下让同一元素反复入栈。我从没见人写对过的单调栈bug就是while循环条件写反把递增栈写成了递减栈答案完全错误。我把常见栈题的类型和对应策略整理成一个速查表题型特征代表题栈的用法核心注意点括号/符号配对有效括号、删除相邻重复项遇到右半部分弹栈配对结束时栈必须为空相邻元素比较每日温度、下一个更大元素单调栈维护候选下标存下标算距离找边界求面积柱状图最大矩形单调栈左右扩展边界首尾加哨兵元素嵌套状态恢复解码字符串、简化路径元组栈/双栈配合出栈顺序是逆序的递归转迭代二叉树遍历、BST迭代器显式栈接管系统调用现场注意左右子树入栈顺序状态枚举回溯括号生成回溯即状态栈思想剪枝条件优先想清楚6.2 什么时候不要用栈避免思维定式栈不是万能的。我用栈写过很多当时觉得很妙、事后发现是错误解法的代码最典型的就是看到最近相邻就条件反射地写栈。实际上有些题用双指针更简单有些题用哈希表更直接。判断标准很简单如果题目要求的是全局的、两两之间的最值或计数优先考虑排序或堆如果是队列式、轮转、BFS层级的处理应该用队列如果只是查找某个特定值时哈希表才是正解。栈的优势永远在于只能看到最近的一个状态这个特性。一旦发现多个状态需要同时比较栈就不再是唯一合理的结构。另外Java里Stack类继承自Vector线程安全但性能有锁开销刷题时更推荐用ArrayDeque或LinkedList模拟栈。C就直接用std::stackPython用list模拟栈是最自然的append和pop都是O(1)没有额外的类要导入。不同语言在栈的使用细节上差异不大真正的差异全在思路是否清晰。6.3 我自己的刷题顺序建议和总结如果你刚开始刷栈题我建议的顺序是先做配对消除类20、1047建立手感再做单调栈入门496、739理解模板然后挑战柱状图最大矩形84和接雨水42最后用二叉树遍历和BST迭代器144、94、173巩固递归转迭代的能力解码字符串394作为嵌套状态的进阶挑战。这套顺序走下来大概20道题左右。栈类的题量不需要很大因为它不像动态规划那样题型千变万化核心规律就那么几条。关键是每一道都要能说清楚为什么用栈以及栈里存的是什么。我自己在模拟面试时被问到栈题从来不会一上来就写代码先花半分钟说一句这是一个典型的单调栈问题我们用下标维护递减序列遇到更大的值就结算答案面试官通常就会点点头。最后分享一个个人体会栈题的调试并不难因为栈是线性的每一步状态都可以打印出来看。写错了不要急把每个循环迭代时栈的内容和答案数组打印出来对着手推一遍绝大多数bug都能一眼找到。这种打印栈状态的调试方法比盯着代码空想快得多。栈是刷题路上最值得先吃透的数据结构之一把上面这些题型过一遍之后再去碰队列、堆、哈希表的组合题你会发现思路顺畅很多。
刷了不少题之后你会发现一个规律栈Stack这个东西看起来是最不起眼的基础数据结构但在实际刷题和面试里的出镜率高得吓人。而且它有个特点——直接考栈操作的题很少真正难的是你根本没想到这题能用栈。LeetCode栈类题目的常见题型其实非常集中套路翻来覆去就那么几套配对消除、单调性维护、递归转迭代、嵌套状态恢复。把这些套路吃透栈相关的中等题基本都能在五分钟内锁定思路。这篇文章我就按题型把栈的常见考法梳理一遍每类都给模板代码和边界坑适合从初级刷到进阶的同学参考。1. 为什么刷栈题要先建立栈感1.1 栈的本质决定了它的三个应用方向栈的核心特性只有一句话后进先出LIFO。但这个特性在不同场景下演化出三种完全不同的用法很多人刷题时觉得栈难是因为把三种用法混为一谈。第一种用法是暂存现场。当我们需要处理嵌套结构、需要记住之前的某个状态以便后面恢复时栈就是天然的草稿纸。比如括号匹配、HTML标签闭合、函数调用栈本质都是遇到一个开始标记压栈记住遇到结束标记弹栈核对。第二种用法是维护单调性。栈内的元素保持严格的递增或递减关系利用这种单调性可以在O(n)时间内解决找下一个更大/更小元素的问题。第三种用法是模拟递归过程。递归在计算机里本来就是靠系统栈实现的当我们把递归改成迭代时就在代码里显式地开一个栈来模拟系统行为二叉树遍历是典型代表。理解这三种方向之后后面所有栈题都能对号入座。1.2 快速判断一道题能否用栈的四条特征实战中判断一道题该不该用栈我总结了四条经验命中任意一条就值得往栈的方向想题目里出现了**相邻元素之间的某种抵消、匹配、比较**关系尤其是连续性的相邻关系。数据存在嵌套结构比如括号套括号、多层路径、重复组合。处理过程需要回退到最近的上一个状态也就是后悔药逻辑。题目暴力解需要反复从后往前看比如每个元素向右找第一个大于它的数。反过来如果题目涉及先进先出、排队轮流处理那应该想队列而不是栈如果只是单纯地找全局最大最小那是排序或堆的事。栈题的关键不在用栈模拟流程而在识别出这是一个需要反向回溯或局部比较的问题。2. 配对消除类栈的消消乐玩法2.1 有效括号与删除相邻重复项同一个模板配对消除是栈最直观的应用。LeetCode第20题有效的括号就是最经典的入门题。它的核心逻辑是左括号入栈右括号出栈并检查是否匹配。任何不匹配或栈空的情况直接返回false。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这里最容易被忽略的是结尾的return not stack。我见过不少人只检查了中间匹配过程忘了最后还要确认栈被清空结果遇到(((这种输入就出错了。栈非空说明有左括号没被匹配字符串无效。第1047题删除字符串中的所有相邻重复项看起来跟括号无关但思路一模一样遍历字符串当前字符和栈顶相同就弹出不同就压入。这就是消消乐的变体——只不过括号题消的是配对的左右括号这题消的是相邻重复字符。def removeDuplicates(s: str) - str: stack [] for ch in s: if stack and stack[-1] ch: stack.pop() else: stack.append(ch) return .join(stack)这道题容易踩的坑是消除之后产生的新相邻重复。比如abbaca这种删掉中间的bb后a和a又相邻了。如果不用栈、直接暴力删字符串还得从头重新扫描。栈的做法天然处理了这种情况——每次只和栈顶比较栈顶就是当前最后一个没被消除的字符删除后新的栈顶自然就是前一个未配对元素不需要回溯扫描。2.2 表达式求值配对消除思想的延伸表达式求值是配对消除的进阶版。第150题逆波兰表达式求值后缀表达式用的是操作数栈遇到数字就压栈遇到运算符就弹出两个操作数计算结果再压回去。def evalRPN(tokens: list[str]) - int: stack [] for t in tokens: if t not in -*/: stack.append(int(t)) else: 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: stack.append(int(a / b)) return stack[-1]两个容易出错的点必须提醒。第一减法除法要注意操作数顺序先弹出的是右操作数b后弹出的是左操作数a写反了结果全错。第二Python的a / b在负数除法时结果可能与预期不符直接用int(a / b)先除后取整比用//更稳妥因为//是向下取整遇到负数是往负无穷方向取整的。更复杂的表达式求值中缀转后缀、带括号的四则运算本质也是两套栈的配合一个操作数栈、一个运算符栈。运算符入栈前先弹出所有优先级不低于它的运算符遇到左括号直接入栈遇到右括号一直弹到左括号。理解了配对消除这个底层逻辑这些变化就都通了。3. 单调栈栈题里含金量最高的一类3.1 下一个更大元素单调栈的入门模板阵单调栈是栈类题目里最值得花时间啃的一块因为它在中等题里的出现频率实在太高。先拿第496题下一个更大元素和第739题每日温度开刀。第739题这样描述给你每天的温度列表返回一个数组每个位置表示要等多少天才能等到更高的温度。def dailyTemperatures(T: list[int]) - list[int]: n len(T) ans [0] * n stack [] for i in range(n): while stack and T[i] T[stack[-1]]: prev stack.pop() ans[prev] i - prev stack.append(i) return ans这个模板的要点是栈里存的是下标不是值。为什么存下标因为我们要算距离天数只有通过下标相减才能得到。栈内元素维持从栈底到栈顶递减的结构也就是所谓的单调递减栈——遇到一个更大的新元素时把栈里所有比它小的旧元素全部弹出同时记录答案。单调性为什么高效因为栈里的元素都是还没找到下一个更大值的候选者。一旦来了更大的值这些候选者统一算账出栈每个元素最多入栈一次、出栈一次整体O(n)。比暴力解法每个元素都要往后扫描O(n^2)快了一个数量级。3.2 柱状图中最大的矩形单调栈的灵魂题第84题柱状图中最大的矩形是单调栈的分水岭。做过这题和没做过这题的面试表现完全两样。给定一组柱子高度找最大矩形面积。核心思路每个柱子作为矩形高度时向左向右扩展到第一个比它矮的柱子就能算出以它为高的最大宽度。用单调栈维护柱子下标保持栈内高度递增从栈底到栈顶。当遇到比自己矮的柱子时说明栈顶柱子右侧边界确定可以结算面积。def largestRectangleArea(heights: list[int]) - int: heights [0] heights [0] stack [] max_area 0 for i in range(len(heights)): while stack and heights[i] heights[stack[-1]]: h heights[stack.pop()] w i - stack[-1] - 1 max_area max(max_area, h * w) stack.append(i) return max_area这里的两个哨兵0是整个解法的灵魂。开头加0保证栈不为空结尾加0保证所有柱子最后都能被弹出结算。如果不加末尾的0最后栈里还会残留一些递增的柱子没计算面积代码会复杂很多。我第一次做这题时踩过一个具体坑结算宽度时w i - stack[-1] - 1这里用的是弹出之后新栈顶的下标。我一开始写成了i - h_index以为宽度是当前柱子和被弹出柱子的距离实际上完全错了。弹出之后再往左看到新栈顶为止才是这个高度的有效宽度范围。3.3 接雨水把单调栈用到极致第42题接雨水是单调栈的集大成者也是面试高频题。暴力解法是每个位置找左右最大高度的较小值减去当前高度累加。单调栈的解法思路是栈内维护递减高度下标当遇到较高的柱子时把栈顶弹出作为坑底此时左右两侧较高的柱子栈内新栈顶和当前柱子形成了U形就能结算这一个坑能接的水量。def trap(height: list[int]) - int: stack [] ans 0 for i, h in enumerate(height): while stack and h height[stack[-1]]: bottom height[stack.pop()] if not stack: break left stack[-1] limited min(height[left], h) - bottom ans limited * (i - left - 1) stack.append(i) return ans这个写法是按层结算水的每次弹出一个坑底计算的是这个高度区间的一小条水量。一定要注意弹出后栈为空的情况说明左侧没有更高的墙了水存不住直接break。接雨水还有双指针和动态规划两种解法单调栈不是空间最优的O(n)空间但它是三种解法中最不容易出错、最容易讲清楚思路的。面试时如果时间紧优先写单调栈版思路顺不容易翻车。我在实际面试模拟中发现能五分钟内写对单调栈版接雨水的人对栈的理解基本到位了。4. 栈与树的组合拳迭代遍历与BST迭代器4.1 为什么递归遍历要改成栈的迭代写法二叉树的前中后序遍历教科书先教递归。但很多面试题要求能否用迭代实现或者题目本身限制了递归深度。递归的底层就是系统栈在维护调用现场我们显式用一个栈来模拟本质上没有换算法只是把隐式的栈变成了显式的栈。前序遍历的迭代写法非常简洁根节点入栈弹出处理先压右孩子再压左孩子。def preorderTraversal(root): if not root: return [] stack [root] res [] while stack: node stack.pop() res.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return res先压右再压左因为栈是LIFO右子树后进会在左子树之后才处理到这正好符合根-左-右的前序顺序。这个细节我见过很多人写反写反就变成先处理右子树了。中序遍历的迭代要稍微绕一点一路往左走并压栈走到空就弹出处理然后转向右子树。def inorderTraversal(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这个一直往左压压到空再回头的模式就是中序遍历的本质。理解这个之后很多需要按中序顺序访问BST节点的题就有基础了。4.2 二叉搜索树迭代器把中序遍历拆成手动版第173题二叉搜索树迭代器要求实现next()和hasNext()每次调用返回BST中序遍历的下一个值。如果直接用数组保存中序结果再依次返回空间是O(n)。面试官通常会追问能不能做到均摊O(h)空间h为树高。其实做法就是把上面的中序遍历拆开初始化时把根到最左端的所有节点压栈next()弹出栈顶并处理其右子树的最左链。class BSTIterator: def __init__(self, root): self.stack [] self._push_left(root) def _push_left(self, node): while node: self.stack.append(node) node node.left def next(self): node self.stack.pop() self._push_left(node.right) return node.val def hasNext(self): return bool(self.stack)这里每次_push_left往栈里推的节点平均下来是O(1)个所以均摊O(h)空间是完全成立的。做这道题最大的收获不是背代码而是理解了递归展开的本质递归到哪里栈的状态就是哪里手动维护栈就等于接管了系统的调用现场。5. 嵌套与回溯类栈的状态恢复进阶玩法5.1 括号生成与回溯把压栈出栈的思想抽象化第22题括号生成让生成n对括号的所有合法组合。这题表面不直接使用栈数据结构但它的核心思想和栈完全一致记录当前左右括号的已用数量通过递归回溯枚举所有可能。回溯本身就是在维护一个状态栈递归进入时是压栈回溯出来是弹栈。def generateParenthesis(n: int) - list[str]: ans [] def backtrack(s, left, right): if len(s) 2 * n: ans.append(s) return if left n: backtrack(s (, left 1, right) if right left: backtrack(s ), left, right 1) backtrack(, 0, 0) return ans这里的剪枝条件right left是核心只要右括号数量小于左括号就可以加右括号如果右括号数量等于左括号加右括号就会产生非法的单独右括号。理解了括号匹配的栈逻辑这个剪枝条件就非常自然了——栈里左括号没被配平之前右括号永远不能超量出现。5.2 解码字符串与简化路径栈处理嵌套状态的典型第394题解码字符串是嵌套恢复类的代表。题目类似3[a2[c]]要解码成accaccacc。难点在嵌套外层的3要作用于内层解码出的字符串。这时候需要两个栈或者一个元组栈数字栈保存重复次数字符串栈保存括号前的已拼接结果。def decodeString(s: str) - str: stack [] for ch in s: if ch ]: tmp [] while stack and stack[-1] ! [: tmp.append(stack.pop()) stack.pop() # 弹出 [ num [] while stack and stack[-1].isdigit(): num.append(stack.pop()) n int(.join(reversed(num))) stack.append(.join(reversed(tmp)) * n) else: stack.append(ch) return .join(stack)这里我吃过一个亏把tmp里的字符弹出后直接reversed(tmp)再拼接但因为弹出顺序是从栈顶往栈底tmp里存的是逆序必须反转回来。如果直接用.join(tmp)会得到完全反过来的字符串。这种弹出顺序天然逆序的坑在栈题里反复出现养成习惯出栈后需要恢复原顺序时第一个动作就是反转。第71题简化路径则是用栈处理路径组件按/切分后遇到普通组件入栈遇到..弹出栈顶组件表示返回上一级遇到.或空字符串忽略。def simplifyPath(path: str) - str: stack [] for part in path.split(/): if part in (, .): continue if part ..: if stack: stack.pop() else: stack.append(part) return / /.join(stack)这道题最容易踩的坑是..之后栈为空的情况。比如路径/../按理说..已经在根目录没法再往上了应该忽略而不是报错。代码里if stack的判断就处理了这个边界。另一个坑是路径末尾的/会split出空字符串必须过滤。这些都体现了栈题的一个共同规律边界条件的判断顺序往往决定了代码能不能一次通过。6. 刷了三年栈题我认为最值得记住的坑与经验6.1 栈题最容易翻车的五个细节第一个是空栈操作。任何stack.pop()或stack[-1]前都要确认栈非空尤其是配对类和结算类的题目。括号匹配题里多了一个多余的右括号单调栈里高处遇到更矮的柱子都可能让栈提前空掉。第二个是栈里存什么。存下标还是存值决定了你能不能在O(1)时间内拿到位置信息。计算距离、宽度时一定要存下标这是每日温度和柱状图最大矩形涨过的教训。第三个是出栈顺序是逆序的。只要从栈里弹出一串元素它们的顺序一定是反的。要在意原顺序时记得反转解码字符串那题就是典型。第四个是哨兵元素。在数组两端放一个边界守卫0或极大值可以避免大量边界判断。柱状图标题在头和尾各加一个0接雨水也可以用类似技巧简化逻辑。用哨兵不是耍小聪明而是真的能减少bug。第五个是复杂度不是假象。单调栈的O(n)是每个元素最多入栈一次出栈一次的均摊结果。写代码时确认这个性质没有被破坏比如嵌套循环里有没有可能在极端情况下让同一元素反复入栈。我从没见人写对过的单调栈bug就是while循环条件写反把递增栈写成了递减栈答案完全错误。我把常见栈题的类型和对应策略整理成一个速查表题型特征代表题栈的用法核心注意点括号/符号配对有效括号、删除相邻重复项遇到右半部分弹栈配对结束时栈必须为空相邻元素比较每日温度、下一个更大元素单调栈维护候选下标存下标算距离找边界求面积柱状图最大矩形单调栈左右扩展边界首尾加哨兵元素嵌套状态恢复解码字符串、简化路径元组栈/双栈配合出栈顺序是逆序的递归转迭代二叉树遍历、BST迭代器显式栈接管系统调用现场注意左右子树入栈顺序状态枚举回溯括号生成回溯即状态栈思想剪枝条件优先想清楚6.2 什么时候不要用栈避免思维定式栈不是万能的。我用栈写过很多当时觉得很妙、事后发现是错误解法的代码最典型的就是看到最近相邻就条件反射地写栈。实际上有些题用双指针更简单有些题用哈希表更直接。判断标准很简单如果题目要求的是全局的、两两之间的最值或计数优先考虑排序或堆如果是队列式、轮转、BFS层级的处理应该用队列如果只是查找某个特定值时哈希表才是正解。栈的优势永远在于只能看到最近的一个状态这个特性。一旦发现多个状态需要同时比较栈就不再是唯一合理的结构。另外Java里Stack类继承自Vector线程安全但性能有锁开销刷题时更推荐用ArrayDeque或LinkedList模拟栈。C就直接用std::stackPython用list模拟栈是最自然的append和pop都是O(1)没有额外的类要导入。不同语言在栈的使用细节上差异不大真正的差异全在思路是否清晰。6.3 我自己的刷题顺序建议和总结如果你刚开始刷栈题我建议的顺序是先做配对消除类20、1047建立手感再做单调栈入门496、739理解模板然后挑战柱状图最大矩形84和接雨水42最后用二叉树遍历和BST迭代器144、94、173巩固递归转迭代的能力解码字符串394作为嵌套状态的进阶挑战。这套顺序走下来大概20道题左右。栈类的题量不需要很大因为它不像动态规划那样题型千变万化核心规律就那么几条。关键是每一道都要能说清楚为什么用栈以及栈里存的是什么。我自己在模拟面试时被问到栈题从来不会一上来就写代码先花半分钟说一句这是一个典型的单调栈问题我们用下标维护递减序列遇到更大的值就结算答案面试官通常就会点点头。最后分享一个个人体会栈题的调试并不难因为栈是线性的每一步状态都可以打印出来看。写错了不要急把每个循环迭代时栈的内容和答案数组打印出来对着手推一遍绝大多数bug都能一眼找到。这种打印栈状态的调试方法比盯着代码空想快得多。栈是刷题路上最值得先吃透的数据结构之一把上面这些题型过一遍之后再去碰队列、堆、哈希表的组合题你会发现思路顺畅很多。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
