刷了不少题之后你会发现一个规律：栈（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::stack，Python用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::stack，Python用list模拟栈是最自然的，append和pop都是O(1)，没有额外的类要导入。不同语言在栈的使用细节上差异不大，真正的差异全在思路是否清晰。6.3 我自己的刷题顺序建议和总结如果你刚开始刷栈题，我建议的顺序是：先做配对消除类（20、1047）建立手感，再做单调栈入门（496、739）理解模板，然后挑战柱状图最大矩形（84）和接雨水（42），最后用二叉树遍历和BST迭代器（144、94、173）巩固递归转迭代的能力，解码字符串（394）作为嵌套状态的进阶挑战。这套顺序走下来，大概20道题左右。栈类的题量不需要很大，因为它不像动态规划那样题型千变万化，核心规律就那么几条。关键是每一道都要能说清楚"为什么用栈"以及"栈里存的是什么"。我自己在模拟面试时被问到栈题，从来不会一上来就写代码，先花半分钟说一句"这是一个典型的单调栈问题，我们用下标维护递减序列，遇到更大的值就结算答案"，面试官通常就会点点头。最后分享一个个人体会：栈题的调试并不难，因为栈是线性的，每一步状态都可以打印出来看。写错了不要急，把每个循环迭代时栈的内容和答案数组打印出来，对着手推一遍，绝大多数bug都能一眼找到。这种"打印栈状态"的调试方法，比盯着代码空想快得多。栈是刷题路上最值得先吃透的数据结构之一，把上面这些题型过一遍之后，再去碰队列、堆、哈希表的组合题，你会发现思路顺畅很多。