企业官网建设流程全解析

Hot 100 你刷到栈这个专题的时候，很容易有种错觉：栈嘛，先进后出，几行代码就能写完，能难到哪去？我一开始也是这么想的。直到我把 Hot 100 里和栈相关的题全部过了一遍，才发现真正拉分的根本不是“会不会用栈”，而是“敢不敢用栈”“什么时候用栈”。括号匹配、表达式求值、单调栈、递归转迭代，每一类背后都是一套完全不同的思考方式。

这篇文章我按自己实际刷题时的顺序来写，先把栈题的题型分布讲清楚，再把 Hot 100 里几道高频题的解法、代码、坑全部拆开揉碎，最后单独写一份调试经验。不适合零基础选手从语法开始学，但只要你写过几道数组题、知道栈是什么，跟着我的节奏走，这一类题基本能理得明明白白。

1. 先聊清楚一件事：Hot 100 里的栈题到底在考什么

1.1 栈题四大类型

我在刷完这些题之后，把栈相关的高频题粗暴分成四类，这个分类帮我省了非常多的时间：

第一类是合法性校验，代表作就是有效的括号。这类题考的是“配对关系”和“顺序关系”，栈天然适合处理嵌套结构。第二类是状态维护，代表作是最小栈、用栈实现队列。这类题其实考的是“辅助结构”，正着用、反着用、组合用，核心是理清楚数据流的走向。第三类是表达式求值，逆波兰表达式、字符串解码、基本计算器都在这一类，考的是优先级和嵌套展开。第四类是单调栈，每日温度、柱状图中最大矩形、接雨水都靠它，这也是栈题里最容易被卡住的地方，因为你不光要维护“进”，还要考虑“出”的时候能结算什么信息。

把这四类理清楚之后你会发现，Hot 100 的栈题并没有跳脱出“模拟 + 数学规律”的范围，只是模拟的套路各不相同。

1.2 识别题目背后套路的经验

我的经验是：读题时先别急着想用不用栈，而是问自己三个问题。

第一个问题，题目里面有没有“嵌套”“配对”“闭合”这些字眼，有的话大概率用栈做合法性校验。第二个问题，题目要求“最近”“上一位”“最靠里”这种和顺序位置强相关的状态，那栈往往能高效维护。第三个问题，如果题目给的是直方图、温度数组这类一维序列，让你求“比当前更大/更小的下一个位置”，并且数据范围到10^5级别，那基本就是在提示你用单调栈。

尤其要警惕第三种。很多人看到数组就只想着双指针、前缀和、滑动窗口，结果一道每日温度用暴力模拟写了个 O(n²)，在 Hot 100 的测试数据下大概率超时。判断是单调栈还是其他方案，一般看两个特征：一是要找的元素满足单调性，二是计算答案时依赖的是一段区间而非单个点。

2. 入门三件套：括号、最小栈、队列互转

2.1 有效的括号

这道题是栈入门的“hello world”，但它的细节坑比很多人想象的要多。我先贴最标准的长这样：

bool isValid(string s) { stack<char> st; unordered_map<char, char> match = { {')', '('}, {']', '['}, {'}', '{'} }; for (char c : s) { if (c == '(' || c == '[' || c == '{') { st.push(c); } else { if (st.empty() || st.top() != match[c]) { return false; } st.pop(); } } return st.empty(); }

我分别强调几个关键点。第一，用哈希表存右括号对应的左括号，比写三组 if-else 清爽得多，后续如果题目扩展出<>这类自定义括号，只需要改表。第二，遇到右括号时一定要先检查栈是否为空，空栈遇到右括号直接返回 false，这一步不少初学会漏掉。第三，循环结束后的return st.empty()不能省，否则"(("这种测试用例会误判成合法。

这道题还有一个常见变种，让你判断“( [ ) ]”是否有效，答案是 false，因为中间出现了交叉闭合。我对这种题的理解是：栈天然保证“最后出现的左括号最先被闭合”，这正是嵌套结构的核心。

2.2 最小栈

设计一个支持push、pop、top、getMin的栈，要求每个操作都是 O(1)。我当时看了一眼就觉得不能每次去遍历找最小值，正确做法是拿两个栈，其中一个专门维护当前位置对应的最小值。

class MinStack: def __init__(self): self.data = [] self.min_stack = [] def push(self, val: int) -> None: self.data.append(val) if not self.min_stack or val <= self.min_stack[-1]: self.min_stack.append(val) def pop(self) -> None: if not self.data: return top = self.data.pop() if top == self.min_stack[-1]: self.min_stack.pop() def top(self) -> int: return self.data[-1] def getMin(self) -> int: return self.min_stack[-1]

这里最容易被忽略的细节是if top == self.min_stack[-1]，判断相等再弹出，这样即便有重复的最小值，也不会把历史最小值提前弹掉。比如连续 push 两个1，辅助栈里可以记录一个1，也可以记录两个1，上面这种写法记录两个，但只在相等时弹出的逻辑不会出错。

我个人比较推荐这种双栈写法，因为可读性强、面试时好解释。当然还有一种“差值法”能省辅助栈空间，但代码可读性差一些，而且遇到负数时要处理溢出，刷题阶段我不建议优先写它。

2.3 用栈实现队列

这题和“用队列实现栈”是一对，Hot 100 里常出现。核心思路就是两个栈倒腾，一个栈专门接收 push 进来的元素，另一个栈专门 pop 时用。只有当输出栈为空时，才把输入栈的所有元素一次性倒过去。

class MyQueue { stack<int> in, out; public: void push(int x) { in.push(x); } int pop() { if (out.empty()) { while (!in.empty()) { out.push(in.top()); in.pop(); } } int res = out.top(); out.pop(); return res; } int peek() { if (out.empty()) { while (!in.empty()) { out.push(in.top()); in.pop(); } } return out.top(); } bool empty() { return in.empty() && out.empty(); } };

我一开始很傻地把每一个 pop 都执行一次倒数据操作，结果大量重复倒腾。正确的做法是“一次倒，多次用”，只有当out为空时才触发倒数据，这样均摊复杂度是 O(1)。队列的先进先出在这里完成了一次“逆序再逆序”，输入栈逆序压入，输出栈再逆序弹出，完美复原顺序，这个思路在后面的字符串解码里还会再遇到。

3. 表达式题：逆波兰、解码、计算器

3.1 逆波兰表达式求值

逆波兰表达式也叫后缀表达式，特点是没有括号，运算符跟在操作数后面。这道题我用栈模拟非常简单：遇到数字就压栈，遇到运算符就弹出两个操作数，运算完再把结果压回去。

def evalRPN(tokens): stack = [] for t in tokens: if t in "+-*/": 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: # 注意这里要用 int(a / b)，不能用 a // b # 因为负数除法 C++ 和 Python 的取整方向不一致 stack.append(int(a / b)) else: stack.append(int(t)) return stack[0]

这里有一个超级大坑：Python 里a // b对负数会向下取整，而题目要求的除法是向零取整。比如-3 // 2 = -2，但题目期望结果是-1。用int(a / b)才能做到向零取整。我在6 / -132这种小数字上踩过一次，后来再也不敢用//处理逆波兰了。

另外要注意弹出顺序，栈顶是右操作数，次顶是左操作数。做减法、除法这些不满足交换律的运算，千万别把a和b写反。

3.2 字符串解码

Hot 100 里的字符串解码，核心形式是"3[a2[c]]"，需要展开成"accaccacc"。括号支持嵌套，这种递归嵌套结构用栈来模拟计算过程特别合适。

我用的双栈思路：一个栈存数字，一个栈存字符串。遇到数字时累加成数字；遇到[时，把当前数字和当前字符串压入各自栈中，然后重置；遇到]时，弹出数字和字符串，做拼接。

string decodeString(string s) { stack<int> numStack; stack<string> strStack; string cur = ""; int num = 0; for (char c : s) { if (isdigit(c)) { num = num * 10 + (c - '0'); } else if (c == '[') { numStack.push(num); strStack.push(cur); num = 0; cur = ""; } else if (c == ']') { int repeat = numStack.top(); numStack.pop(); string prev = strStack.top(); strStack.pop(); for (int i = 0; i < repeat; i++) { prev += cur; } cur = prev; } else { cur += c; } } return cur; }

这个写法里，cur始终表示“当前正在处理的那一层字符串”，遇到[时把外层状态保存，遇到]时恢复并完成重复拼接。我一开始犯了一个错误：算完一个右括号后，把结果直接塞进cur，却没有和前面已经解析过的字符串合并，结果嵌套场景全错。上面代码最核心的就是prev += cur，它把当前层结果接回到外层的尾部。

还有一个小技巧：不计较数字是多少位，直接num = num * 10 + (c - '0')，在遇到[之前它都是一位一位累积的，三位数、四位数都能正确处理。

3.3 基本计算器

严格来说，带括号的全量计算器不一定在 Hot 100 里每个版本都出现，但它是表达式题的集大成版本。实现思路是：用两个栈或者一个栈，遇到数字累加，遇到+-设置符号位，遇到(把当前结果和符号压栈，遇到)弹出来计算。

int calculate(string s) { stack<int> st; int res = 0; int sign = 1; int num = 0; for (int i = 0; i < s.size(); i++) { char c = s[i]; if (isdigit(c)) { num = num * 10 + (c - '0'); } if (c == '+' || c == '-' || c == ')' || i == s.size() - 1) { res += sign * num; num = 0; if (c == '-') sign = -1; if (c == '+') sign = 1; if (c == ')') { // 弹出括号前的符号和括号前的结果 res = st.top() * res + ... } } } return res; }

写这道题时我踩过最大的坑是括号处理：res += sign * num是先把括号内的结果算好，遇到右括号后，需要把括号前的符号取出来，和括号内的结果相乘，再加上括号前的累积结果。很多人把“括号前结果”和“括号内结果”混在一处，导致括号层级一多，算出来就是乱的。我建议做这题之前先无脑写成纯逆波兰的流程，也就是先在脑子里把中缀转成后缀，再用栈模拟，这样思路会更顺。

4. 单调栈专题：从每日温度到接雨水

4.1 每日温度

题目是给你每天的天气温度，让你返回一个数组，每个位置表示“要等多少天才能等到更高的温度”。暴力做很简单，两重循环，但数据量一大就会被卡。

单调栈的做法是：维护一个栈，栈底到栈顶保持递减。遍历温度数组时，如果当前温度比栈顶温度高，说明栈顶元素等到了第一个比自己高的天，弹出并结算下标差。

def dailyTemperatures(temperatures): n = len(temperatures) ans = [0] * n stack = [] for i in range(n): while stack and temperatures[i] > temperatures[stack[-1]]: idx = stack.pop() ans[idx] = i - idx stack.append(i) return ans

这里有两个细节。第一个，栈里存的是下标，不是温度本身，因为我们要算天数差。第二个，当前温度等于栈顶温度时不处理，直接把当前下标入栈，这样保证栈里的元素严格递减，等于的情况留给更后面的温度去触发。

我当时第一次做的时候，不是找“下一个更大”，而是想维护一个“窗口最大值”，这是错误的方向。每日温度其实是在问“右边第一个大于我的位置”，这和单调栈是完美匹配。

4.2 柱状图中最大的矩形

这题是单调栈里最容易绕晕的一道。它要你找最大的矩形面积，做法还是单调栈，但栈内维护的是递增关系。每次遇到一个比栈顶矮的柱子，就弹出栈顶，以它的高度为矩形高，以左右边界作为宽来结算。

int largestRectangleArea(vector<int>& heights) { // 前后补 0 能避免最后栈里残留元素 heights.insert(heights.begin(), 0); heights.push_back(0); stack<int> st; st.push(0); int res = 0; for (int i = 1; i < heights.size(); i++) { while (heights[i] < heights[st.top()]) { int h = heights[st.top()]; st.pop(); int w = i - st.top() - 1; res = max(res, h * w); } st.push(i); } return res; }

写这题时，我一开始不懂为什么要前后补 0。补 0 的作用是强制让所有柱子都能被迫出栈。尾部补 0，可以让整个遍历结束后栈里所有元素都被结算；头部补 0，可以让最左侧的矩形计算时st.top()始终有值，不用单独判断空栈。

还有一个容易出错的点：宽度是i - st.top() - 1，不是i - 弹出的下标。因为弹出后，新的栈顶就是矩形左边界，而右边界是当前i。这个宽度公式要配合画图理解，硬背很容易记错。

4.3 接雨水

接雨水最经典的单调栈思路和柱状图正好相反，它用递减栈。遍历高度时，如果当前高度比栈顶高，说明形成了一个水坑的最低点，此时需要弹出栈顶，看它左右两边的墙能蓄多少水。

int trap(vector<int>& height) { stack<int> st; int res = 0; for (int i = 0; i < height.size(); i++) { while (!st.empty() && height[i] > height[st.top()]) { int bottom = st.top(); st.pop(); if (st.empty()) break; int left = st.top(); int w = i - left - 1; int h = min(height[left], height[i]) - height[bottom]; res += w * h; } st.push(i); } return res; }

我第一次写这个 while 循环时没有if (st.empty()) break，结果弹出唯一栈顶后直接访问st.top()报错。这里当bottom左侧没有墙时，雨水根本存不住，所以必须 break。

接雨水的宽度计算和前面的矩形类似，也是i - left - 1，但高度不同，接雨水的高度取决于两侧墙的较小值减去底的高度。每一次弹出只结算当前这一层水，不是一次性结算一整块水体，这也是理解接雨水的关键。用按层计算的方式去想，“每一层水”都会在某个低点被弹出时结算一次，最后累加就是总面积。

Daily 温度、最大矩形、接雨水这三道题我强烈建议放在一起刷。它们都是“找左边或右边第一个更小/更大的位置”这一大类问题，区别只在于：结算的是距离还是面积，维护的是递增还是递减。把单调栈这个底层思维打通之后，这三道题基本能一口气背出代码框架。

5. 栈的边界与扩展：扁平化嵌套列表与循环数组

5.1 扁平化嵌套列表迭代器

Hot 100 里还有一类栈题不直接考计算，而是考“怎么模拟递归”。扁平化嵌套列表就是典型代表，它给你一个[1, [2, [3, 4], 5]]这样的结构，要求实现一个迭代器，每次返回一个整数。

一个很常见的实现：用一个栈来保存已经反转过的元素，每次取时如果栈顶还是列表，就继续展开。

class NestedIterator: def __init__(self, nestedList): self.stack = list(reversed(nestedList)) def next(self): return self.stack.pop().getInteger() def hasNext(self): while self.stack: top = self.stack[-1] if top.isInteger(): return True self.stack.pop() lst = top.getList() for item in reversed(lst): self.stack.append(item) return False

这个解法的妙处在于：hasNext负责把栈顶的列表展开成整数，next直接弹出即可。展开时用reversed保证原顺序。我一开始在做这道题时，想用递归把所有整数提前拍平存到数组里，但这违背了迭代器“惰性求值”的语义，而且在深层嵌套时初始化时间太长。用栈的实时展开才符合题目精神。

5.2 循环数组和单调栈的配合

有一个高频变种：在循环数组里找下一个更大元素，也就是数组尾部再接一个同样的数组。这种做法最常见的就是把索引遍历到2 * n，用i % n取真实下标，其他逻辑照搬每日温度的单调栈。

def nextGreaterElements(nums): n = len(nums) ans = [-1] * n stack = [] for i in range(2 * n): idx = i % n while stack and nums[idx] > nums[stack[-1]]: ans[stack.pop()] = nums[idx] if i < n: stack.append(i) return ans

这里有个小细节：只有第一次遍历时才能入栈，第二次遍历只触发弹出结算，否则同一个下标会重复入栈导致死循环或者错误结果。第一次遍历时栈里的元素已经能覆盖所有“向右看”的情况，第二次遍历就纯用来结算那些在末尾还单调递增、一直没弹出的元素。

6. 常见坑与调试经验

6.1 四个高频翻车点

栈题代码量不大，但翻车点非常固定。第一个翻车点是访问栈顶前不判空，每当写st.top()之前都要先问自己：现在栈会不会为空？尤其在双栈、while 循环里，很容易弹着弹着弹空了。第二个翻车点是宽度的边界计算，接雨水和最大矩形的宽度公式方向相反，建议自己手动跑一组小用例，不要靠背。第三个翻车点是单调栈的方向，求“下一个更大”用递减栈，求“下一个更小”用递增栈，方向写反整个答案就乱套。第四个翻车点是表达式题里的操作数顺序，减法除法注意谁在左边谁在右边，连续栈模拟时必须先弹出右操作数。

6.2 调试栈题的小技巧

我在本地调试栈题时，习惯把每个栈在每一步操作后都打印出来。类似这种日志：

处理到 i=4, 当前栈: [1, 3, 5]，弹出 5，结算 ans[3]=1

把栈的内容打印出来之后，很多“明明逻辑没问题结果不对”的题都能一眼看出问题。尤其是单调栈，打印几轮之后你就会清楚地看到“谁弹出谁结算”的过程。

还有一个小技巧：把测试用例改成极端小数据，比如[2, 1, 5, 6, 2, 3]这种，自己拿着纸笔画一遍栈的变化，比对代码输出。别嫌这种笨办法慢，栈题出错往往就是边界条件一两个下标的问题，手推一遍比看半天 debug 日志快得多。

关于空间复杂度的优化，我多说一句：很多栈题用辅助栈解决后，面试官会追问“能不能不用额外空间”。最小栈的差值法、队列双栈翻转、单调栈用下标代替值，都是常见的优化方向。刷题阶段先把辅助栈写对，再想优化不迟。

最后再分享一个我个人的习惯：我把 Hot 100 里栈相关的题分成“括号类、表达式类、单调栈类、模拟类”四个小集合，每刷完一类就重新写一遍代码框架，不抄答案、纯默写。反复两三轮之后，再遇到新题也不会慌，因为思路基本都能套进这四类的骨架中。栈这东西看着基础，它其实是很多复杂问题的最小模型，用熟练了非常划算。