刷算法题刷到一定量之后你会发现一个很有意思的现象栈这个数据结构教材里讲起来就三句话——后进先出、只能从栈顶进出、底层可以用数组或链表实现。你觉得自己已经懂了可真到了做题的时候尤其是面试那种白板环境下十道栈相关的题目里至少有四五道会让你卡住。不是不理解栈而是不知道什么时候该用栈、该往栈里压什么、该在什么时机弹出。这篇就把栈这个专题拆开揉碎从基础行为模式到单调栈、括号匹配、表达式求值再到真正容易出错的边界细节系统地过一遍。适合正在刷题准备面试的开发者也适合想把自己代码里“能用栈却用了暴力解法”的片段优化掉的人。1. 栈的基本行为模式为什么看似简单却总在题目中翻车1.1 从生活直觉到代码抽象栈的核心就一个词后进先出LIFO。你递归调用的函数栈、浏览器的后退页面、编辑器里的撤销操作本质上都是栈。算法题里最常见的栈题反而不是让你直接实现一个栈而是让你识别出“当前问题具备回溯最近状态的特性”然后自然地用栈去模拟。我见过太多人拿到栈相关的题目第一反应是把所有数据先一股脑压进栈里再一股脑弹出来然后发现完全没利用到栈的核心能力。真正的栈题考的是你在扫描数据的过程中什么信息值得留在栈里等待未来的匹配以及什么时候该把栈里过时的信息清掉。1.2 栈的三大抽象整理这几年遇到的题目栈在算法题里其实只干三件事配对左右括号、HTML标签、温度变化中的“下一个更高值”都是某种形式的左右配对。栈负责暂存左侧未匹配的信息遇到右侧时再配对弹出。回溯DFS、递归改迭代、迷宫寻路需要记住“来时的路”栈天然存储了这条路径。单调化把乱序数据加工成单调序列丢失部分信息换取查询效率这是单调栈的核心思想。一个合格的栈题解通常都会落到这三大抽象之一。如果你的思路不在这三类里大概率是审题方向错了。1.3 一个基础题的两种写法对比拿“反转字符串”这种入门题举例。初级写法是def reverse_string(s): stack list(s) res while stack: res stack.pop() return res这段代码没有任何问题但它没有展现出栈的必要性。反转字符串用双指针更直接栈在这里只是“用了个数据结构”而不是“非用不可”。真正的栈题比如括号匹配你不给栈就很难优雅解决。所以做题时要先问自己这个题里需要回看“最近的一段历史”吗如果需要栈就是候选方案如果只是全局反转、全局统计那栈很可能不是最优解。2. 单调栈最有“题感”的一类栈问题2.1 单调栈到底在干什么单调栈是栈里最常见的考点也是很多人第一次感受到“栈的威力”的地方。它维护一个栈内元素单调递增或单调递减的序列在扫描数组的每个元素时通过弹出入栈操作解决一类“找某个元素左边/右边第一个比它大/小的元素”的问题。一句话概括单调栈用空间换时间把两重循环的暴力解法降成O(n)。经典应用场景是“每日温度”这类题给你每天的温度要求输出每一天要等几天才能等到更高温度。暴力做法对每一天往后扫最坏O(n²)。单调栈的做法是维护一个栈栈底到栈顶温度递减遇到比栈顶温度高的日子就说明栈顶等到了答案。2.2 模板代码与易错点下面这个代码片段是“下一个更大元素”的通用模板我建议直接背下来然后理解每一行为什么这么写。def next_greater_elements(nums): n len(nums) res [-1] * n stack [] # 栈里存的是下标 for i in range(n): while stack and nums[stack[-1]] nums[i]: idx stack.pop() res[idx] nums[i] stack.append(i) return res有两个地方经常有人写错单独说一下栈里存的是下标不是值。存下标的好处是你既能通过下标拿到值又能直接定位到结果数组的位置。存值的话答案对应的位置还需要额外映射很容易乱。判断条件用的是还是取决于题目要求“严格大于”还是“大于等于”。如果要求严格大于那么相等元素不弹出因为相等元素不是答案反过来如果要求“大于等于”相等元素也要弹出。这个细节决定结果的正确性面试时考官特别喜欢在这里设置陷阱。2.3 为什么用单调栈就能保证O(n)直观理解数组里每个下标最多入栈一次、出栈一次所以总操作次数是O(n)。从语义上说每次弹出都意味着“找到了当前栈顶元素的答案”后面再也不会需要它了所以弹出是安全的。这种“每个元素处理一次过时即弃”的模式和滑动窗口的维护思路很像。区别在于滑动窗口淘汰靠的是位置单调栈淘汰靠的是大小关系或者数值关系。做题时能分清这一点思路会清晰很多。2.4 接雨水与柱状图最大矩形单调栈的两类变体这两个题目是单调栈的进阶题网上题解很多但很多人只是背代码没搞懂原理。简单拆一下接雨水雨水能存住是因为形成了凹槽凹槽的两边是更高的柱子。单调递减栈扫描时每当遇到比栈顶高的柱子就说明栈顶柱子和当前柱子之间形成了一个可储水的凹槽凹槽高度由“左右两侧较矮的那根”决定宽度由下标距离决定。柱状图最大矩形矩形的高受限于最矮的柱子。用单调递增栈维护一个高度序列当弹出当前最矮柱子时它的左右边界就是栈内前一个元素和当前扫描到的元素矩形面积就能稳定计算。这两个题一个是“找两边更高确定水面”一个是“找两边更矮确定边界”方向相反但用的都是同一个单调栈框架。建议把模板和这两个题放在一起刷理解会深很多。3. 括号匹配与嵌套结构从模拟到状态设计3.1 为什么计数器替代不了栈很多人一开始做有效括号这道题会想用一个整数计数器遇到左括号加1遇到右括号减1最后检查是否为0。这个思路对“只有一种括号、只要求数量配对”的简单场景有效但一旦引入多类型括号立刻失效。比如([)]这种序列用计数器检查会发现左右括号数量相等但它并不是一个合法嵌套结构[)明显错位。括号类题目真正考的是最近的未匹配左括号是什么类型而不是“有多少个左括号没匹配”。栈恰好提供了“查看最近未匹配项”的能力。3.2 有效括号的完整模拟用栈模拟有效括号逻辑非常清晰def is_valid(s): stack [] pair {): (, ]: [, }: {} for ch in s: if ch in pair: # 右括号 if not stack or stack[-1] ! pair[ch]: return False stack.pop() else: # 左括号 stack.append(ch) return not stack三个关键点值得认真体会遇到右括号时先判栈是否为空。如果为空说明右括号没有对应的左括号直接返回False。这一步最容易漏漏掉的后果是stack[-1]访问报错或者更隐蔽地返回错误结果。栈顶元素和当前右括号配对而不是栈里任意一个左括号配对。“最近”是这个逻辑的精髓。遍历结束后栈必须为空。栈里还剩左括号说明有括号从没被闭合。3.3 进阶最长有效括号怎么用栈“最长有效括号”比“有效括号”难一个档次因为你要找的是最长的连续合法长度而不是判断整个串是否合法。用栈的做法有一个很巧妙的点栈底放一个哨兵下标。初始时压入-1表示“上一个未匹配的位置的前一个位置”。扫描过程中遇到左括号压入下标遇到右括号先弹出栈顶。如果弹出后栈为空说明当前右括号没有匹配对象它自己成为一个新的“未匹配边界”把当前下标压进去如果栈不为空则当前有效长度为i - stack[-1]用它更新答案。这个技巧的精髓在于你并不是在每个左括号匹配时才计算长度而是利用栈内剩余元素作为边界计算长度。栈里的元素始终代表“当前这段连续有效括号串的起点前一位”。理解了这一点代码只是几行但思维含金量很高。3.4 从括号到字符串解码括号匹配的一个常见变形是字符串解码比如输入3[a2[bc]]输出accbcbc。这类题目的核心是括号里可能有数字、有括号、有字母你需要分层处理。做法是维护两个栈一个数字栈、一个字符串栈。遇到数字就压数字栈遇到左括号就把当前已拼接的字符串压入字符串栈遇到右括号时弹出两栈进行拼接。这里之所以要用栈是因为括号可以嵌套内层的结果需要和外层的内容拼接这个拼接顺序天然和栈的调用顺序一致。把这道题和有效括号一起刷基本就能把“栈处理嵌套结构”的关键点拿全。4. 表达式求值栈在运算优先级中的应用逻辑4.1 中缀表达式为什么难以直接计算我们平时写的表达式3 4 * 2叫中缀表达式运算符在两个操作数中间。计算机处理起来最大的麻烦是优先级不能看到加号就立即计算因为后面可能还有乘号优先级更高。这本质上是需要回看上一次未完成的操作又是一个典型的栈场景。解法有两个流派一种是把中缀表达式转成后缀表达式逆波兰表达式再对后缀表达式求值另一种是用两个栈直接对中缀表达式边扫描边计算。两种方法都值得掌握这里先讲后缀表达式路线。4.2 逆波兰表达式求值最简单的栈应用后缀表达式里运算符跟在操作数后面比如3 4 2 * 。求值时不需要关心优先级因为优先级已经在转换时被处理成顺序了。def eval_rpn(tokens): stack [] for token in tokens: if token in -*/: b stack.pop() a stack.pop() if token : stack.append(a b) elif token -: stack.append(a - b) elif token *: stack.append(a * b) else: stack.append(int(a / b)) else: stack.append(int(token)) return stack[0]这里有两个细节很容易出错弹出顺序和运算顺序相反。a - b里先弹出的b是右操作数后弹出的a是左操作数。写反了结果完全不对尤其减法和除法。除法要处理负数。不同语言对负数整除的定义不同刷题时要看清楚题目要求是向零取整还是向下取整。Python的int(a / b)是向零取整而a // b是向下取整很多人在这个细节上栽过。4.3 中缀转后缀运算符优先级栈中缀转后缀的经典算法是用栈保存运算符遇到数字直接输出遇到运算符则弹出栈中优先级不低于当前运算符的所有运算符再把当前运算符压入栈。遇到左括号压栈遇到右括号则弹出到左括号为止。下表是常用的运算优先级参考运算符优先级结合性、-1左结合*、/2左结合括号最高—转换过程本质上就是“把该延后的运算压入栈中等到合适的时机再计算”。实际面试写代码时我建议不要死记算法而是记住一个原则**只有当中缀表达式里的下一个运算符优先级不高于栈顶运算符时才能把栈顶运算符弹出并输出。**用这个原则推演几个例子自然就记住了。4.4 双栈法直接计算中缀表达式如果你想绕开“先转后缀再求值”的两步走可以直接用两个栈一个数字栈、一个运算符栈。扫描中缀表达式时遇到数字压数字栈遇到运算符当运算符栈栈顶的优先级不低于当前运算符时就反复弹出栈顶运算符和两个操作数进行计算结果压回数字栈直到无法弹出再把当前运算符压入运算符栈遇到左括号压运算符栈遇到右括号则一直弹出计算到左括号。这种双栈法的好处是贴近人的直觉而且可以处理带括号的复杂表达式。代价是逻辑分支比后缀求值多容易漏掉“每次计算后结果要立刻压回数字栈”这一步。做题时如果时间紧张我推荐先写后缀表达式路线代码更短、出错率更低。这里的核心收获是**凡是涉及优先级、嵌套、延迟计算的场景栈都是顺理成章的工具。**抓住“延迟”这个关键词表达式求值就不会觉得神秘了。5. 栈题目的边界条件与实战避坑清单5.1 空栈操作第一大坑所有栈相关的题目最常见的运行时错误都来自对空栈执行pop或取栈顶操作。有效括号那节已经提到过判断右括号前要先检查栈是否为空。但空栈的问题不止出现在那里单调栈里也可能出现比如所有元素都在递减那么栈永远不会被弹出此时如果误以为栈顶有值就会出事。我的习惯是**每次写stack.pop()或stack[-1]前先问自己一句“这个位置栈一定是非空吗”**如果答案不确定就加一层判断。宁可代码多一行if也不要在测试用例上踩空栈异常。5.2 存值还是存下标栈里存值还是存下标是很多人写题时犹豫的点。总结下来就两条如果只要比较大小存值足够如果需要定位结果位置或者需要计算间距存下标需要值时通过下标访问。单调栈由于通常要返回每个位置对应的答案所以存下标几乎成了标准做法。而在简单的括号匹配里存字符本身更直接。做题时先确认答案需要什么维度再决定栈里存什么不要一上来就默认存值。5.3 相等元素的处理一个容易被忽略的决策点很多人在写单调栈时没有想过当新元素和栈顶元素值相等时到底要不要弹出栈顶这个决定绝不是随意的它直接影响题目要求“第一个大于”还是“第一个大于等于”的语义。举个例子题目如果问“下一个比当前元素大的元素”那相等元素就不应该作为答案所以弹出条件必须是严格小于当前元素相等时不能弹。反之如果问“下一个不小于当前元素的值”相等元素也算找到了答案那就要用小于等于作为弹出条件。把这个逻辑搞清楚笔试面试时遇到“怎么改模板适应新需求”的追问就不会慌了。5.4 变形题最小栈与用栈实现队列栈的变形题里最常考的两个是最小栈要求O(1)时间内完成入栈、出栈、获取最小元素。经典做法是维护一个辅助栈每次入栈时把当前最小值一起压进去。具体来说辅助栈栈顶始终保存主栈当前所有元素的最小值入栈时比较新元素和辅助栈栈顶把较小值压入辅助栈。这样主栈弹出时辅助栈同步弹出两个栈永远同高度逻辑简单不易错。用栈实现队列核心是“双栈倒腾”。入队时往输入栈压出队时如果输出栈为空就把输入栈所有元素弹出并压入输出栈此时栈顶就是最早入队的元素。摊还复杂度是O(1)每个元素至多被压入和弹出两次。这类变形题考的仍然是栈的基本操作但多了一层“用数据结构的组合去模拟另一种抽象”的思考。建议把它们放在栈专题复习的尾声做用于检验自己是否真的理解栈的push和pop时机。5.5 什么时候该想到用栈最后给一个经验性的判断清单。遇到下面的信号优先往栈的方向想题目出现“配对”“嵌套”“最近”“历史”“回溯”等关键词数据是线性排列但处理逻辑有明显的“先来后处理”特征答案需要回看之前扫描过的信息而且只需要回看最近的一段暴力解法是O(n²)你觉得应该能优化成O(n)。把这些信号和前面的几类题对应起来做题时的方向感会强很多。栈不是万能的但在这些问题上是性价比最高的选择。最后再分享一个我自己的练习心得栈的题目千万不要只看题解一定要自己手写几遍尤其是单调栈和表达式求值这两类。写的过程中你会暴露很多自以为懂了其实没懂的点比如弹出条件的等号问题、空栈判断、下标和值的混用。这些坑踩一遍并改正比看十篇题解都管用。等你能够不假思索地写出单调栈模板再遇到括号、解码、求值这类变体基本就是改两行条件的事。
