企业官网建设流程全解析

刷算法题刷到一定量之后，你会发现一个很有意思的现象：栈这个数据结构，教材里讲起来就三句话——后进先出、只能从栈顶进出、底层可以用数组或链表实现。你觉得自己已经懂了，可真到了做题的时候，尤其是面试那种白板环境下，十道栈相关的题目里至少有四五道会让你卡住。不是不理解栈，而是不知道什么时候该用栈、该往栈里压什么、该在什么时机弹出。这篇就把栈这个专题拆开揉碎，从基础行为模式到单调栈、括号匹配、表达式求值，再到真正容易出错的边界细节，系统地过一遍。适合正在刷题准备面试的开发者，也适合想把自己代码里“能用栈却用了暴力解法”的片段优化掉的人。

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

有两个地方经常有人写错，单独说一下：

1. 栈里存的是下标，不是值。存下标的好处是，你既能通过下标拿到值，又能直接定位到结果数组的位置。存值的话，答案对应的位置还需要额外映射，很容易乱。
2. 判断条件用的是<还是<=，取决于题目要求“严格大于”还是“大于等于”。如果要求严格大于，那么相等元素不弹出，因为相等元素不是答案；反过来，如果要求“大于等于”，相等元素也要弹出。这个细节决定结果的正确性，面试时考官特别喜欢在这里设置陷阱。

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 中缀转后缀：运算符优先级栈

中缀转后缀的经典算法是：用栈保存运算符，遇到数字直接输出，遇到运算符则弹出栈中优先级不低于当前运算符的所有运算符，再把当前运算符压入栈。遇到左括号压栈，遇到右括号则弹出到左括号为止。

下表是常用的运算优先级参考：

转换过程本质上就是“把该延后的运算压入栈中，等到合适的时机再计算”。实际面试写代码时，我建议不要死记算法，而是记住一个原则：**只有当中缀表达式里的下一个运算符优先级不高于栈顶运算符时，才能把栈顶运算符弹出并输出。**用这个原则推演几个例子，自然就记住了。

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)。

把这些信号和前面的几类题对应起来，做题时的方向感会强很多。栈不是万能的，但在这些问题上是性价比最高的选择。

最后再分享一个我自己的练习心得：栈的题目千万不要只看题解，一定要自己手写几遍，尤其是单调栈和表达式求值这两类。写的过程中你会暴露很多自以为懂了其实没懂的点，比如弹出条件的等号问题、空栈判断、下标和值的混用。这些坑踩一遍并改正，比看十篇题解都管用。等你能够不假思索地写出单调栈模板，再遇到括号、解码、求值这类变体，基本就是改两行条件的事。