栈算法核心：单调栈、表达式求值与回溯递归的实战指南

1. 先把栈的本质聊透：不只是“先进后出”

栈这个数据结构，几乎所有写代码的人第一天就见过，但真正到算法题里能把它用明白的，其实不多。很多朋友问我“栈怎么刷题”，我的回答永远是：先把三个场景啃透，单调栈、表达式求值、回溯递归，剩下的基本都是这三块的变形。这篇内容就当是个人经验总结，适合正打算刷 LeetCode、准备算法面试的朋友，也适合平时写业务代码但想补一补算法底子的人，尤其是那些一看到“栈”就只会做括号匹配、一到变体题就懵的读者。

真正理解栈，不能只记住“先进后出”这四个字。你得知道它到底在什么场景下能提供价值，为什么很多算法不用递归，却还是要靠一个栈结构来完成。下面我先用自己的理解把这层窗户纸捅破，再进入具体的算法题套路。

1.1 栈的两种“打开方式”：函数调用栈与显式栈

栈在程序里其实有两个完全不同的身份。第一种是函数调用栈，也就是 C/C++ 里的调用栈帧、Java 虚拟机栈、Python 的 call stack。每次调用函数，系统会把返回地址、局部变量、参数压进去，函数返回时再弹出去，天然就是 LIFO。理解了这一点，你就能理解递归为什么能“自动回溯”：不是有什么神奇的力量，而是每次递归调用都会开一个新的栈帧，上一层所有的状态都被保存在栈帧里，等下一层返回后才能继续。

第二种是你自己定义、自己往里 push/pop 的显式栈。算法题里说到“栈”，绝大多数时候指的是这种容器。我见过很多人把这两种混在一起讲，结果越学越乱。其实两者是互补的：递归依赖系统栈，你不需要自己管；而显式栈则是你把递归改成迭代、把状态主动保存起来的关键工具。比如二叉树非递归遍历、括号匹配、表达式求值、单调栈，用的都是显式栈。

我个人建议你学栈相关算法题时，先在纸上画出递归函数调用的栈帧变化，再去理解显式栈的 push/pop 顺序。你会发现很多题的思路其实就是在模拟“系统栈”：你不递归，但心里仍然有一个栈在保存“还没做完的事情”，这个视角是看懂所有栈题的核心。

1.2 栈在算法题里的常见应用场景

栈不是孤立的数据结构，它的应用场景其实非常具体。我总结下来，刷题中比较高频的场景有六类：括号匹配与嵌套结构处理；算术表达式求值、后缀表达式转换；单调栈相关的一维数组问题；DFS、回溯算法的显式栈实现；二叉树非递归遍历；以及类似“撤销操作”“逐层嵌套解析”等模拟题。

括号匹配是最熟悉的入门题，核心思路是：遇到左括号就压栈，遇到右括号时判断栈顶是否匹配。这个套路看似简单，但变形很多，比如括号的嵌套层数、有效括号的最长长度、带通配符的括号匹配，都是它衍生出来的。表达式求值则是把运算优先级和括号结合进来，用两个栈分别存数字和运算符，或者先转后缀再统一计算。单调栈我单独放在后面讲，因为它值得拥有自己的章节。

除了算法题，栈思想在工程里也有非常直观的体现：浏览器的前进后退、IDE 的撤销重做、代码编辑器里的花括号匹配，都是基于栈。即使是全栈项目里谈到的“技术栈”，虽然含义不同，但你熟悉这些数据结构时，再看各种框架的底层原理也会更容易。所以我一直觉得，栈算法不只是为了面试，它真的在帮你建立“状态管理”的直觉。

1.3 手写栈还是直接用 STL？

刷题时到底用系统提供的栈还是自己写一个数组模拟栈？我的建议是：如果只是平时刷题，直接用std::stack（C++）或 Python 的list都完全没问题；但如果你准备参加竞赛，或者同一道题里有大量入栈出栈操作，我更推荐用数组模拟栈。原因是std::stack默认基于deque，虽然方便，但在极端压力下常数偏大，而且不好打印调试；数组模拟则简单高效，代码量也就多一行。

数组模拟栈的常见写法是这样的：

# Python 用 list 即可，天然是栈 stack = [] stack.append(1) # push stack.append(2) top = stack[-1] # peek stack.pop() # pop

// C++ 数组模拟栈，适合竞赛 int stk[100005], top = 0; stk[++top] = 1; // push int cur = stk[top]; // peek top--; // pop

注意我写的是stk[++top]，不是stk[top++]。这里有个新手常踩的坑：如果用stk[top++] = 1去 push，那么 top 始终指向栈顶元素的下一个位置，访问stk[top]时拿不到栈顶，必须先top--。我个人的习惯是“top 永远指向最后一个有效元素”，这样读代码时更直观，边界判断也不会乱。如果你选择“top 指向下一个空位”，那全套循环都要对应调整，一定要保持风格统一，不要混用。

2. 单调栈：最值得优先掌握的栈技巧

在栈相关的题型里，单调栈是性价比最高、最值得优先掌握的一类。为什么这么说？因为它解决的问题很典型：在一维数组中，快速找到每个元素左边或右边第一个比它大/比它小的元素。暴力做法很容易想，两层循环就能写，但复杂度是 O(n²)；数据量一旦到十万、百万级别，暴力就直接超时。单调栈的复杂度是 O(n)，每个元素最多入栈一次、出栈一次，代码写起来又不长，所以各大厂的面试题和 LeetCode 高频题里都大量出现。

2.1 单调栈到底在求什么

单调栈，从名字上看就是“栈内元素保持单调性”，常见的有单调递增栈和单调递减栈。这里说的递增递减，通常指从栈底到栈顶的排序。单调递增栈就是栈底最小、栈顶最大；单调递减栈就是栈底最大、栈顶最小。

它的精髓不只在于“维护单调”，更在于“利用出栈时机”。当你想要让新元素入栈时，为了保持单调性，你得把前面破坏单调性的元素弹出。这些被弹出的元素，恰好是在“遇到新元素时”做出了历史使命。所以不要只记住“往里压”，要记住关键点：每个元素出栈的那一瞬间，意味着它找到了一个“答案”或“贡献”的机会。

我画一段最经典的模板：找每个元素右边第一个比它大的元素。从右往左遍历，维护一个单调递减栈，或者从左往右遍历，都可以。下面是我常用的一种写法，按“当前元素与栈顶比较”来决定出栈：

def next_greater(nums): n = len(nums) res = [-1] * n stack = [] # 存储下标，栈顶到栈底递减 for i in range(n): while stack and nums[i] > nums[stack[-1]]: idx = stack.pop() res[idx] = i stack.append(i) return res

这里while stack and nums[i] > nums[stack[-1]]表示每当遇到一个更大的元素，就把栈里较小元素弹出，并记录答案。这样所有元素只进出一轮，复杂度 O(n)。很多人问为什么要存下标而不是直接存值，因为很多后续计算需要用到距离或者索引差，存下标更灵活。

2.2 单调递增还是单调递减，怎么判断

每次写单调栈，都会在“递增还是递减”上卡一下。我的一个土办法是：直接判断你关心的是“第一个比它大”还是“第一个比它小”。

如果是找右边第一个比当前元素大的，那么栈内的元素在被弹出时，是因为遇到一个比自己大的元素，说明栈内方向应该是“从栈底到栈顶递减”；如果你找的是右边第一个比当前元素小的，那么栈内方向反过来，从栈底到栈顶递增。不要死记“求大就递减，求小就递增”之类的顺口溜，最好在每次做题时用一个小例子手动模拟一遍。

我调试时也常用一个非常笨但有效的方法：先写一个 O(n²) 的暴力验证函数，再用随机小数组对比结果。一旦单调栈函数和暴力结果不匹配，立刻打印“准备入栈的元素、当前栈内下标、结果数组”，一般一两次就能找到方向反了还是边界写错。这个方法我强烈建议你用，不要觉得自己写的是标准模板就不可能错，实际动手时很容易因为一个等号写错，得到完全不同的答案。

2.3 三个经典实战场景

最常用到的三个题目，我按从易到难的顺序整理如下：LeetCode 739 “每日温度”、LeetCode 42 “接雨水”、LeetCode 84 “柱状图中最大的矩形”。

每日温度要求求每个元素之后第一个更高温度的距离，本质就是找右边第一个比它大的元素。因为我需要距离，所以栈里存下标，而不是值。从左往右遍历，如果当前温度高于栈顶温度，就把栈顶弹出，答案填上i - stack[-1]。其余元素继续等待。这道题非常适合作为单调栈入门第一题，因为你只需要理解“出栈即找到答案”。

接雨水稍微复杂一点，常见解法用单调递减栈。从左到右遍历高度，当当前高度大于栈顶高度时，说明找到了一个“坑”的右边界，可以开始计算雨水量。这时弹出栈顶作为低点，新的栈顶作为左边界，宽度就是两个边界下标的差，高度是两边高度的较小值减去当前低点高度。这个思路是“横向计算每一层的水量”，初看不太直观，但代码跑通后你会觉得非常巧妙。

柱状图中最大的矩形是另一个方向的题目：找每个柱子左边第一个比它矮的、右边第一个比它矮的，这样就能确定这个柱子能向左右扩展多远，然后计算面积。这里常用单调递增栈，并在数组两端加上高度为 0 的哨兵，保证所有元素都能正常出栈。我贴上核心模板：

def largest_rectangle_area(heights): heights = [0] + heights + [0] # 哨兵 stack = [] ans = 0 for i in range(len(heights)): while stack and heights[i] < heights[stack[-1]]: h = heights[stack.pop()] left = stack[-1] ans = max(ans, h * (i - left - 1)) stack.append(i) return ans

这里哨兵非常关键。没有哨兵，最后一个元素可能永远不会出栈，导致漏算；没有左边哨兵，取stack[-1]时可能报栈空。经验之谈：写单调栈题目时，优先考虑是否要在数组两端补哨兵值，这能帮你避免一大堆边界判断。

3. 表达式求值：栈的经典战场

第二个必须吃透的场景是表达式求值，这也是很多大学“编程题实训”里的经典实验，比如“基于栈的算术表达式求值算法”。表面上它只是个课程设计，实际上它是面试里常见的进阶题：支持加减乘除、括号、多位数字，甚至负数。理解了它，你对栈的掌控会上一个台阶，因为你需要同时维护数字栈和运算符栈，还要处理优先级。

表达式求值一般有两种主流思路。第一种先把中缀表达式转成后缀表达式，也就是逆波兰式，再用栈统一计算；第二种直接用双栈，边扫描边按优先级计算。两种都值得掌握，我下面分头拆解。

3.1 中缀转后缀（逆波兰式）

中缀表达式是“1 + 2 * 3”，人一看就懂，但计算机很难处理优先级。后缀表达式“1 2 3 * +”则方便多了：遇到数字就压栈，遇到运算符就弹出两个数计算结果，再压回去。所以第一步是把中缀转成后缀。

转换规则我并不建议死记，用一句话理解：从左到右扫描，数字直接输出；运算符则和栈顶运算符比优先级，当前运算符优先级不高于栈顶时，先把栈顶弹出，再把新运算符压栈；遇到左括号直接压栈，遇到右括号则弹出到左括号为止。代码大致是：

def infix_to_postfix(exp): priority = {'+': 1, '-': 1, '*': 2, '/': 2} stack = [] output = [] tokens = exp.split() for t in tokens: if t.isdigit(): output.append(t) elif t == '(': stack.append(t) elif t == ')': while stack and stack[-1] != '(': output.append(stack.pop()) stack.pop() # 弹出左括号 else: while stack and stack[-1] != '(' and priority[t] <= priority[stack[-1]]: output.append(stack.pop()) stack.append(t) while stack: output.append(stack.pop()) return output

这段代码里有个细节：比较优先级时我用的是priority[t] <= priority[stack[-1]]，不是<。如果你用<，那么相同优先级的运算符不会被弹出，导致原本应该从左到右计算的结果被改变。比如2 - 3 + 4，如果相同优先级不弹出，转成后缀后可能变成2 3 4 + -，结果是 -5，但正确答案是 3。这是表达式求值里非常经典的一个坑，笔试时很容易踩。

3.2 双栈直接求中缀表达式

如果不想转后缀，也可以直接用一个数字栈和一个运算符栈同时处理。大流程是：扫描数字时压入数字栈；扫描运算符时，先看一下运算符栈顶是否优先级不低于当前运算符，如果是就先把栈顶的运算算掉，再压入当前运算符；扫描到左括号直接压栈，扫描到右括号就把括号内的运算符全部算完。扫描结束后，再把运算符栈里剩下的运算符依次算完。

双栈的代码会比转后缀多一点点，但好处是不用额外生成后缀表达式，面试写起来更直接。核心代码框架如下：

def calculate(tokens): nums = [] ops = [] priority = {'+': 1, '-': 1, '*': 2, '/': 2} def calc(): b = nums.pop() a = nums.pop() op = ops.pop() if op == '+': nums.append(a + b) elif op == '-': nums.append(a - b) elif op == '*': nums.append(a * b) else: nums.append(a // b if a * b >= 0 else -(-a // b)) for t in tokens: if t.isdigit(): nums.append(int(t)) elif t == '(': ops.append(t) elif t == ')': while ops and ops[-1] != '(': calc() ops.pop() else: while ops and ops[-1] != '(' and priority[t] <= priority[ops[-1]]: calc() ops.append(t) while ops: calc() return nums[-1]

注意这里的除法我特意处理了向零取整，因为在 Python 里-3 // 2得到的是 -2，而标准算数表达式求值期望的是 -1。你如果用 C++，int除法会自动向零截断，反而没问题。这种语言特性差异，正是很多人把本地能跑的代码交上去却 WA 的原因。

3.3 容易翻车的边界情况

表达式求值看似简单，实际能挂的地方非常多。第一个是数字多位，比如123 + 456，如果你一位一位读数字，必须临时拼数，不能遇到一个数字就压栈。第二个是负号与减号的区分：当负号出现在表达式开头，或者紧跟在左括号后面时，它是一元负号，不是二元减法。处理方式可以是在负号前补一个 0，让它变成减法，比如-3+2改写成0-3+2，这样就统一了。第三个是除数为 0、整数溢出、括号未匹配、操作数不足，这些在实际测试样例里都会出现。

我建议你在完成基本实现后，自己多补几组测试用例：

这些用例不仅是给程序找 bug，也是在帮你把“栈的执行顺序”真正想清楚。我刷题这么多年，最深的体会是：表达式求值的核心不是代码量，而是对“什么时候该算”的判断，这个判断练熟了，栈题基本上就通了一半。

4. 回溯与 DFS：栈的隐形存在

很多同学做回溯题时，总觉得那是“递归”专题，和栈没什么关系。但当你画出递归调用树，就会发现每一次递归调用其实就是一次入栈，每一次 return 就是一次出栈。回溯算法的“撤销状态”操作，本质上就是在恢复上一层调用栈保存的现场。

LeetCode 里大量排列、组合、子集问题，比如全排列、组合总和、N 皇后，都依赖这个思想。如果你只是在递归函数里改了一个全局数组，却忘记在递归返回时恢复，那么状态就会“污染”到下一次尝试。处理这种问题的标准套路是：递归前修改状态，递归后立刻撤销修改。

4.1 递归调用栈与回溯的本质

举个最简单的全排列例子。假设数组是[1,2,3]，你想输出所有排列。第一个位置选了 1，然后递归处理[2,3]；递归返回后，你得把 1 从当前排列里移除，才能让第一个位置尝试 2。这个“移除”操作就是回溯，它对应的是系统栈弹出的过程。

如果你用显式栈来模拟递归，那么“当前路径”和“剩余可选集合”都必须作为状态保存下来。这里比递归麻烦，但好处是你能直观地看到栈里存了哪些中间状态。我用一个简化伪码来说明概念：

# 显式栈模拟 DFS stack = [(0, [])] # (当前层, 当前排列) while stack: level, path = stack.pop() if level == len(nums): result.append(path) continue # 注意栈是后进先出，所以要逆序压入 for x in reversed(nums): if x not in path: stack.append((level + 1, path + [x]))

这里(level, path)就类比了递归栈帧：每一帧知道自己在哪一层、已经选了哪些数。用递归做时，这些状态由系统保存；用显式栈做时，这些状态由你自己塞进栈里。理解这个对应关系之后，你再去看“递归改迭代”“非递归前序遍历”这类题，会立刻清晰很多。

4.2 从递归到显式栈的通用转换思路

如果面试官要求你不能用递归，或者题目数据规模大到递归会爆栈，你就要会手动用栈模拟。我的通用方法是三步走。第一步，明确递归状态：一个函数调用所依赖的所有关键参数是什么，比如当前节点、当前路径、当前访问到的位置。第二步，把这些状态打包成一个元组或结构体，作为栈帧元素。第三步，把递归里的“进入下一层”改成“向栈里压入新状态”，把 return 改成“从栈里弹出当前状态”。

举个例子，二叉树的前序遍历，递归写法非常短：

def preorder(root): if not root: return visit(root) preorder(root.left) preorder(root.right)

显式栈写法就是：

def preorder(root): if not root: return [] stack = [(root, 0)] result = [] while stack: node, visited = stack.pop() if not node: continue if visited == 0: result.append(node.val) # 第一次访问 stack.append((node, 1)) stack.append((node.left, 0)) stack.append((node.right, 0)) return result

这里我用(node, visited)来区分是“第一次访问节点”还是“访问完毕要回退”。这个技巧特别适合处理需要二次操作的中序、后序遍历。很多人一看到非递归遍历的代码就头疼，其实你只要意识到栈帧存的是“当前状态 + 下一步干什么”，就能看成是递归的忠实翻译。

4.3 调用栈崩溃：从算法题到工程实战

栈相关的问题不仅在刷题时出现，工程里最经典的“栈溢出”也值得专门讲一讲。当递归层数过多，系统栈空间耗尽，C++ 会段错误，Python 会抛出RecursionError，Java 会StackOverflowError。很多人以为这只是“递归层数太深”，但在实际项目中，触发因素往往很隐蔽，比如深度优先遍历一个超大的目录树、解析嵌套非常深的 JSON、或者在 event loop 里反复调用同一个异步函数。

定位这类问题，我的第一个建议是：先打印当前递归深度，看它到底涨到多少才爆。C++ 的默认栈空间在 Windows 上通常只有 1MB 左右，Linux 常见是 8MB，一个栈帧如果因为局部数组太大占到几 MB，那么递归根本不需要多层就直接崩了。Python 的递归限制默认是 1000 层，但如果你每个栈帧里放了大数组，几百层也可能出事。

遇到系统栈不够时，不要硬调大栈空间，优先考虑两种方案。一种是把递归改成显式栈的迭代写法，这需要你理解前面说的“状态打包”思路；另一种是检查递归函数里是否有不必要的局部大对象，能不能移到堆上。很多工程里的“爆栈”根本不是递归次数太多，而是你把一个很大的临时数组放在递归函数里，每次调用都复制一份。这个坑在 C++ 里尤其常见，我见过的线上崩溃案例有一半都出在“局部对象太大”上。

5. 常见问题与排查技巧实录

写栈题最容易出现的问题，其实翻来覆去就那么几类。这里我整理一套自己平时排障时用的方法，希望能帮你少走弯路。

5.1 栈空判断与边界条件

第一个高频问题：在stack[-1]之前没有判断栈是否为空。C++ 里访问空栈的栈顶是未定义行为，Python 里直接抛IndexError。解决办法很简单——在取栈顶前先检查not stack。单调栈里经常会写while stack and ...，这个stack and一定不能丢。我见过不少初学者把条件精简掉，结果用例一多就挂。

第二个高频问题：单调栈的索引边界。存储下标时，弹出后栈可能为空，此时再取stack[-1]就会出错。我的习惯是在弹栈之后立刻判断栈是否为空，为空时答案可以直接置为-1或者0，不为空时再取最新的栈顶作为左边界。如果你使用哨兵，这个问题会得到很大缓解，但哨兵本身也有自己的位置要求，不能乱加。

第三个高频问题是重复元素。求“右边第一个比它大”和“右边第一个大于等于它”，代码只差一个等号，结果完全不同。刷题时一定要看清题目说的是“大于”还是“大于等于”，否则即使逻辑看起来“差不多”，测试用例也会教你做人。

5.2 单调栈方向写反的辨法

我提供一个固定的排查流程。首先，选一组最简单的小数组，比如[2,1,3]，手工算出每个位置目标答案。然后，把单调栈代码里的每一步 push/pop 都打印出来，对比手工执行。最后，重点看“出栈条件”与“更新答案的位置”是否与题目定义一致。如果找“下一个更大的数”却一直得到较小的数，基本就是把递增递减写反了，或者把>写成了<。

手动模拟时，我常用的表格形式如下：

这种表看起来简单，但能极大降低调试成本。你不需要在脑子里空转，把状态写下来，问题往往一眼就看出来。

5.3 一个速查表：栈题常见崩溃与对策

我整理了栈相关算法题里最常见的五个“崩溃点”，以及对应的对策，方便你复习时快速对照：

还有一个非常隐蔽的坑：如果你用 Python 的list当栈，.pop()之前没有判断长度，那么当栈内没有元素时就会报错。C++ 的std::stack::top()则不会主动报错，但结果是不可预测的，线上排查会更痛苦。所以我建议在调试阶段写一个peek_or_none(stack)这样的辅助函数，宁可多写几行，也不要让空栈问题潜伏在长逻辑里。

6. 刷题建议与个人经验

栈的知识点说多不多，说少也不少。最后这部分我想根据自己的刷题经验，给出一条比较靠谱的路线和学习习惯，帮你把前面的内容真正内化成能力，而不是背模板。

6.1 推荐的栈题刷题顺序

如果你从零开始刷栈相关题目，我建议按下面的顺序来。第一阶段先把最基础的“括号匹配”“栈的模拟”做透，目标是建立“遇到嵌套就想到栈”的条件反射。第二阶段做主栈和最小栈相关的题，比如用两个栈实现队列、设计一个支持getMin的栈，这类题考的是你对栈特性的灵活运用。第三阶段进入单调栈，从“每日温度”开始，再做“接雨水”和“柱状图中最大矩形”。第四阶段做表达式求值，中缀转后缀、基本计算器。第五阶段做 DFS、回溯的栈模拟题目。

具体题目我常用的清单是：LeetCode 20、155、225、232、496、739、42、84、150、224、394、946。这几道题覆盖了栈的基础、单调栈、表达式求值和字符串解析几大方向，难度正好从简到难。把这些题弄明白，基本上面试里遇到的栈题都能找到思路。

学习时要多做一件事：看完题解后，不要直接跳到下一题，把这道题改成“如果限制条件变弱/变强，代码要怎么变”。比如“每日温度”如果改成求“左边第一个更小元素”，代码只需要把遍历方向或比较符号换一下，这个练习能让你真正掌握单调栈，而不是只记住这一题的答案。

6.2 我的调试习惯和一个小建议

最后分享一点个人在实际做题里的习惯。第一，凡是栈相关的题，我先写“手动模拟表格”再写代码，尤其是单调栈和有重复元素的情况，哪怕是道简单题，我也至少推一遍。第二，我建议在本地调试时用数组模拟栈，而不是直接调用std::stack，因为数组可以打印出全部内容，而std::stack只能看到栈顶，不利于定位问题。第三，出栈时先想清楚“我要不要用这个出栈元素来更新答案”，如果答案更新发生在入栈时，那大概率思路就错了。

还有一个我自己踩过很多次坑后的心得：写栈的循环时，不要急着优化代码行数。单调栈里while和if的区别、先出栈再取新栈顶的顺序，一旦写错就会在隐蔽的数据上失败。先用最啰嗦、最明确的写法保证正确，再逐步精简，这个顺序不能反。

如果你能把“递归调用栈”和“显式栈”这两条线串起来看，再配合单调栈和表达式求值里的实战练习，我相信任何栈相关的算法题都不会再让你发怵。栈这个数据结构本身不复杂，复杂的是你对“状态什么时候保存、什么时候恢复”的判断，而这份判断力，只能靠一次次手动模拟和踩坑积累起来。