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) { stackchar st; unordered_mapchar, 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 { stackint 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) { stackint numStack; stackstring 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) { stackint 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(vectorint heights) { // 前后补 0 能避免最后栈里残留元素 heights.insert(heights.begin(), 0); heights.push_back(0); stackint 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(vectorint height) { stackint 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 调试栈题的小技巧我在本地调试栈题时习惯把每个栈在每一步操作后都打印出来。类似这种日志处理到 i4, 当前栈: [1, 3, 5]弹出 5结算 ans[3]1把栈的内容打印出来之后很多“明明逻辑没问题结果不对”的题都能一眼看出问题。尤其是单调栈打印几轮之后你就会清楚地看到“谁弹出谁结算”的过程。还有一个小技巧把测试用例改成极端小数据比如[2, 1, 5, 6, 2, 3]这种自己拿着纸笔画一遍栈的变化比对代码输出。别嫌这种笨办法慢栈题出错往往就是边界条件一两个下标的问题手推一遍比看半天 debug 日志快得多。关于空间复杂度的优化我多说一句很多栈题用辅助栈解决后面试官会追问“能不能不用额外空间”。最小栈的差值法、队列双栈翻转、单调栈用下标代替值都是常见的优化方向。刷题阶段先把辅助栈写对再想优化不迟。最后再分享一个我个人的习惯我把 Hot 100 里栈相关的题分成“括号类、表达式类、单调栈类、模拟类”四个小集合每刷完一类就重新写一遍代码框架不抄答案、纯默写。反复两三轮之后再遇到新题也不会慌因为思路基本都能套进这四类的骨架中。栈这东西看着基础它其实是很多复杂问题的最小模型用熟练了非常划算。