企业官网建设流程全解析

刷 LeetCode Hot 100 的人，大概都会经历这样一个阶段：数组、链表题还能靠记忆硬磨，可一旦看到标签里写着“栈”，心里就开始没底。栈的概念很简单——先进后出，可在真题里它一会儿出现在括号匹配，一会儿变成接雨水，一会儿又藏在字符串解码里。这篇内容我没有打算把每道题的标准答案原样贴一遍，而是想和你聊聊怎么把 Hot 100 里的栈题串成几条线索：什么时候你要想到栈、单调栈到底在算什么事、带括号的表达式题怎么处理、最小栈这类设计题为什么常考。适合刚刷完基础题准备冲 Hot 100 的人，也适合二刷想建立体系的开发者。

1. 先搞清楚栈在 Hot 100 里到底解决什么问题

栈在计算机里几乎无处不在。函数调用本身就是栈，A 调用 B、B 调用 C，C 先返回，B 再返回，A 最后收尾，这就是典型的调用栈行为。你写递归时，每一次调用都会生成一个栈帧，保存返回地址和局部变量，等函数执行完，栈帧弹出，控制权交回上一层。所以算法题里凡是带有“嵌套”“等待后处理”“成对闭合”这类特征的问题，都天然适合用栈。

很多人觉得栈题难，是因为题目包装得很花哨。但 Hot 100 里的栈题，本质上只围绕四件事打转：

• 括号匹配、配对消除，靠栈的先进后出特性处理最近匹配。
• 寻找下一个更大/更小的元素，靠单调栈维护候选序列。
• 表达式求值、字符串解码，靠栈保存“现场”，方便括号结束后恢复外层状态。
• 设计类题目，比如最小栈，靠辅助栈或差值记录来满足时间复杂度约束。

1.1 一个朴素的判断方法：看到什么样的题该想到栈

我在刷题时给自己总结过一个很粗糙的“信号词”清单。不需要背，看到题目出现下面这些特征，第一反应就该考虑栈：

比如20. 有效的括号就是最纯粹的“配对消除”题。左括号入栈，右括号看栈顶是否匹配，匹配就弹出，不匹配直接返回 false；最后栈必须是空的。这个解法不需要背，理解“最近匹配”四个字就能自己推出来。

1.2 Hot 100 栈题全景：先看地图再动刀

我不建议按题号顺序刷，先按题型分组更高效。Hot 100 里常见的栈题可以分成这么几类：

看起来每道题差别很大，但共同要回答的问题只有一个：当前这个状态，要不要留到后面再处理？如果答案是肯定的，栈就是最顺手的数据结构。

2. 单调栈系列：Hot 100 里最值钱的套路

单调栈是栈专题里性价比最高的内容。Hot 100 里至少有三道题（每日温度、接雨水、柱状图中最大矩形）是同一个套路的不同马甲。单调栈的核心思想是：栈内元素保持单调（递增或递减），当你遍历到新元素时，不停弹出破坏单调性的元素，利用弹出的时机计算答案。每个人最多入栈一次、出栈一次，所以整体时间复杂度是 O(n)，空间复杂度 O(n)。

2.1 每日温度：单调栈最小实现模板

先看739. 每日温度。题目是给一组温度，让你求每个温度之后多少天会出现更高温度，没有则填 0。暴力做法是每个位置往后扫描，O(n^2)；用单调递减栈，一遍遍历就能解决。

public int[] dailyTemperatures(int[] temperatures) { int n = temperatures.length; int[] ans = new int[n]; Deque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i < n; i++) { while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) { int idx = stack.pop(); ans[idx] = i - idx; } stack.push(i); } return ans; }

栈里存的是下标，不是温度值，因为我们要算天数差。栈从底到顶保持递减：栈顶是当前未找到答案的、最新的日子。新来了一个更高的温度，说明栈顶这个下标终于等到了第一个比自己暖的天，弹出并记录距离。每个元素只会被弹出一次，所以总时间是 O(n)。

画一下例子：[73, 74, 75, 71, 69, 72, 76, 73]，i=0 直接入栈；i=1 时温度 74 比栈顶 73 大，弹出 0，答案ans[0]=1，再入栈 1。整个过程就是不断把“悬而未决”的旧下标弹出结算。

做这类题的关键转换是：你不需要为每个元素向后找，而是让每个元素在弹出时被它右边第一个更大的元素结算。思路从“给定一个点找右边界”变成“每到一个新点，结算所有以它为右边界的状态”，这是个非常美妙的视角转换，适应后很多单调栈题都能秒。

2.2 柱状图中最大的矩形：单调栈怎么求“边界”

84. 柱状图中最大的矩形和每日温度不一样，它找的不是下一个更大元素，而是每个柱子作为高度时，左边第一个更矮的柱子和右边第一个更矮的柱子。这两个边界之间的距离，就是当前柱子高度能扩展的最大宽度。

最直观的做法是用两个数组记录左右边界：

public int largestRectangleArea(int[] heights) { int n = heights.length; int[] left = new int[n]; int[] right = new int[n]; Deque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i < n; i++) { while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) { stack.pop(); } left[i] = stack.isEmpty() ? -1 : stack.peek(); stack.push(i); } stack.clear(); for (int i = n - 1; i >= 0; i--) { while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) { stack.pop(); } right[i] = stack.isEmpty() ? n : stack.peek(); stack.push(i); } int ans = 0; for (int i = 0; i < n; i++) { ans = Math.max(ans, heights[i] * (right[i] - left[i] - 1)); } return ans; }

这里为什么要弹大于等于当前高度的元素？因为我们要找“更矮”的边界，等于当前高度的柱子遮挡不了当前柱子的扩展，反而会把边界算错。用>=弹出等于的元素，是在相等元素中取最右边那一个作为边界，保证计算出来的宽度是包含等高的扩展范围。

这个写法清晰，但要开两个数组。更简洁的做法是在数组前后各加一个高度为 0 的哨兵，一次遍历搞定：

public int largestRectangleArea(int[] heights) { int n = heights.length; int[] h = new int[n + 2]; for (int i = 0; i < n; i++) { h[i + 1] = heights[i]; } Deque<Integer> stack = new ArrayDeque<>(); int ans = 0; for (int i = 0; i < h.length; i++) { while (!stack.isEmpty() && h[stack.peek()] > h[i]) { int cur = stack.pop(); ans = Math.max(ans, h[cur] * (i - stack.peek() - 1)); } stack.push(i); } return ans; }

尾部哨兵 0 的作用非常关键：遍历结束时，栈里可能还留着递增的柱子，哨兵 0 会把它们全部弹出，逐一结算。这样可以保证没有漏算。栈里存的下标，自底到顶对应的高度是递增的，所以弹出的cur的左右边界就是栈内前一个元素和当前i，宽度直接i - stack.peek() - 1就能算出来。

2.3 接雨水：横向接水的栈解法

42. 接雨水在 Hot 100 里属于“你必须会”的题目。双指针解法是按列累计，单调栈解法是按层累计，后者更贴近栈的思维。

public int trap(int[] height) { int ans = 0; Deque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i < height.length; i++) { while (!stack.isEmpty() && height[i] > height[stack.peek()]) { int bottom = stack.pop(); if (stack.isEmpty()) { break; } int left = stack.peek(); int width = i - left - 1; int h = Math.min(height[left], height[i]) - height[bottom]; ans += width * h; } stack.push(i); } return ans; }

这里维护的是单调递减栈。当新元素比栈顶高时，意味着出现了一个可以积水的位置：栈顶是坑底，新的i是右边界，弹掉坑底之后新的栈顶是左边界。积水高度取左右边界的较低者减去坑底高度，宽度是左右边界之间的距离。

对比 84 和 42 能发现一个有趣现象：84 是找更矮的边界来限制面积，42 是找更高的边界来形成凹槽。一个单调递增、一个单调递减，方向完全相反。刷题时最容易错的就是单调方向搞反，我建议每次都先想清楚：我现在是想让栈顶成为“被新元素触发结算”的对象，还是想让它成为“夹在新元素和栈内元素之间”的被测对象。想清楚这个，方向自然就定了。

3. 表达式与字符串解码：栈的另一个大主场

除了单调栈，Hot 100 里还存在一类和解析有关的栈题，典型代表是224. 基本计算器和394. 字符串解码。这类题的核心不是单调性，而是“现场保护”：遇到左括号意味着一个子问题开始，需要把外层结果和状态存起来；遇到右括号意味着子问题结束，恢复外层继续算。

3.1 基本计算器：用栈保存符号与临时结果

224. 基本计算器的题目约束是只有加减法和括号，没有乘除。难度标注 Hard，并不是因为算法复杂，而是细节多：空格、负号、嵌套括号一起出现，很容易绕晕。

我的处理思路是把减法理解为“加上一个负数”，这样整个表达式就变成一系列带符号的数字求和。遇到括号时，把当前累计结果res和当前符号sign压栈，然后重置res=0、sign=1去处理括号内部；遇到右括号，括号内计算完的结果乘以上一层符号，再加上之前保存的res。

public int calculate(String s) { int res = 0, sign = 1, num = 0; Deque<Integer> stack = new ArrayDeque<>(); for (char c : s.toCharArray()) { if (Character.isDigit(c)) { num = num * 10 + (c - '0'); } else if (c == '+') { res += sign * num; num = 0; sign = 1; } else if (c == '-') { res += sign * num; num = 0; sign = -1; } else if (c == '(') { stack.push(res); stack.push(sign); res = 0; sign = 1; } else if (c == ')') { res += sign * num; num = 0; res *= stack.pop(); res += stack.pop(); } } if (num != 0) { res += sign * num; } return res; }

注意两个细节。一个是循环结束后别忘了把最后一个数累加进去，因为表达式可能不以符号结尾。另一个是右括号结算时，res += sign * num这句必须在弹出之前执行，否则括号内最后那个数字会丢失。我见过好几个人在这里漏掉，导致答案差一位。

如果想再加深理解，可以接着刷227. 基本计算器 II，它把加减法升级成带乘除的版本，需要额外维护一个栈来存乘除结果。两题一起刷，基本就把表达式解析这一类套路吃透了。

3.2 字符串解码：模拟“展开嵌套括号”

394. 字符串解码的输入像3[a2[c]]，输出是accaccacc。这题用递归也能写，但显式双栈更直观。

public String decodeString(String s) { Deque<Integer> countStack = new ArrayDeque<>(); Deque<StringBuilder> strStack = new ArrayDeque<>(); StringBuilder cur = new StringBuilder(); int k = 0; for (char c : s.toCharArray()) { if (Character.isDigit(c)) { k = k * 10 + (c - '0'); } else if (c == '[') { countStack.push(k); strStack.push(cur); cur = new StringBuilder(); k = 0; } else if (c == ']') { int repeat = countStack.pop(); StringBuilder prev = strStack.pop(); for (int i = 0; i < repeat; i++) { prev.append(cur); } cur = prev; } else { cur.append(c); } } return cur.toString(); }

这里两个栈分别存“括号外已经拼好的字符串”和“当前的重复次数”。每次遇到[，就把当前cur和k都压进去，开始一个新片段；遇到]，把新片段重复指定次数后接到之前保存的字符串后面。这样从内向外一层层展开，完全模拟了递归调用的现场保存与恢复。

理解这题的关键是：不要试图一次性拼出整个答案，把括号当作函数调用的边界，左边是返回地址，右边是返回值。这样想，双栈的合理性就很自然了。

4. 设计题与递归回溯：栈不只是用来算题目

Hot 100 里有一道直接考“栈设计”的题目：155. 最小栈。平时常听人说要刷“全栈项目”，这个词里的“栈”和算法里的“栈”完全是两回事，但在算法题里，栈作为数据结构的设计题，考察的是你对栈操作时间复杂度和状态维护的敏感度。

4.1 最小栈：辅助栈方案与差值法

题目要求设计一个栈，除了 push、pop、top 之外，还要在 O(1) 时间内返回栈内最小值。最直观的方案是维护一个辅助栈，同步保存“当前栈内元素的最小值”：

class MinStack { Deque<Integer> data = new ArrayDeque<>(); Deque<Integer> min = new ArrayDeque<>(); public void push(int val) { data.push(val); if (min.isEmpty()) { min.push(val); } else { min.push(Math.min(min.peek(), val)); } } public void pop() { data.pop(); min.pop(); } public int top() { return data.peek(); } public int getMin() { return min.peek(); } }

辅助栈的巧妙之处在于，它和主栈的深度完全同步，栈顶始终是当前所有元素里的最小值。pop 时两个栈同步弹出，不会出现历史最小值丢失的问题。代码简单，面试时最好先给这个版本，讲清楚思路再加优化。

更进阶的差值法也值得知道：主栈里不存原始值，存当前值与当前最小值的差值。如果差值小于 0，说明新的值成为新的最小值。这样做省掉了一个辅助栈空间，但数据类型需要用 long，否则差值可能溢出。思路很巧，但实际工程里意义不大，更适合用来在面试中展示你对数据关联的理解。

4.2 栈帧、回溯与显式栈的对应关系

栈在递归和回溯里的位置经常被忽略。一个回溯算法的递归调用过程，本质上是系统的调用栈在帮你保存“尝试到哪一步了”。每次进入递归，系统压入一个栈帧，保存当前局部变量；返回时，栈帧弹出，又回到之前的状态。这就是“回溯”名字的由来。

如果忘记递归写法，你可以用显式栈模拟。比如二叉树前序遍历：

Deque<TreeNode> stack = new ArrayDeque<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); // 访问 node if (node.right != null) stack.push(node.right); if (node.left != null) stack.push(node.left); }

注意这里要先压右子树再压左子树，因为栈是后进先出，先压右边的，左边才能先被弹出，正好保持根左右的遍历顺序。显式栈里存的是“还没访问的子树入口”，访问完一个节点后，它的左右子树入口就互换了顺序，这正是调用栈在递归里的行为模式。

理解这层关系后，回头看“backtrace 栈回溯”这种说法就不会觉得玄乎。它就是指利用栈的保存状态能力，让算法可以一条路走到黑，再原路退回尝试另一条路。算法框架没变，变的只是表现方式。

5. 常见坑位与排查清单

栈相关的题代码量不大，但极容易在小细节上翻车。我把自己踩过和见过的坑整理成了一张排查表，刷题时卡住了直接对照找原因。

还有一些经验我可以直接分享：

第一，刷栈题时手边放一张纸，模拟栈的进出过程。尤其是单调栈，画几轮比看十遍题解都有用。栈里每个元素什么时候入、什么时候出，出栈时你拿到了什么信息，这张图会告诉你所有答案。

第二，不要对“有效的括号”这类简单题掉以轻心。用它当热身，可以迅速检测自己是否还习惯栈的基本操作。我在面试时见过有人会把右括号误写成入栈条件，这种低级错误很致命。

第三，可以按这个顺序刷：20 有效的括号 -> 155 最小栈 -> 739 每日温度 -> 42 接雨水 -> 84 柱状图中最大的矩形 -> 394 字符串解码 -> 224 基本计算器。每一步都比前一步节奏快，到基本计算器时你会自然发现前面练的括号和现场保存能力全都在这里汇合了。

栈这个专题是 Hot 100 里投入产出比很高的内容。题型套路固定，边界坑就那几类，被它折磨一两次之后，后面再遇到“候选者很多，新来的一个元素要清算旧元素”的场景，你都会下意识想到单调栈；再遇到“嵌套子问题需要保留外层状态”的场景，你也会下意识想到用栈保存现场。如果现在正卡在某一题上，别急着翻题解，先把它归到我前面分好的类型里去，想想这个状态适不适合栈，再动手写。多数情况下，你会发现自己已经能独立写出一大半了。