LeetCode Hot 100栈题全攻略:从单调栈到表达式解析一网打尽

发布时间:2026/11/19 10:00:17

LeetCode Hot 100栈题全攻略:从单调栈到表达式解析一网打尽 刷 LeetCode Hot 100 的人大概都会经历这样一个阶段数组、链表题还能靠记忆硬磨可一旦看到标签里写着“栈”心里就开始没底。栈的概念很简单——先进后出可在真题里它一会儿出现在括号匹配一会儿变成接雨水一会儿又藏在字符串解码里。这篇内容我没有打算把每道题的标准答案原样贴一遍而是想和你聊聊怎么把 Hot 100 里的栈题串成几条线索什么时候你要想到栈、单调栈到底在算什么事、带括号的表达式题怎么处理、最小栈这类设计题为什么常考。适合刚刷完基础题准备冲 Hot 100 的人也适合二刷想建立体系的开发者。1. 先搞清楚栈在 Hot 100 里到底解决什么问题栈在计算机里几乎无处不在。函数调用本身就是栈A 调用 B、B 调用 CC 先返回B 再返回A 最后收尾这就是典型的调用栈行为。你写递归时每一次调用都会生成一个栈帧保存返回地址和局部变量等函数执行完栈帧弹出控制权交回上一层。所以算法题里凡是带有“嵌套”“等待后处理”“成对闭合”这类特征的问题都天然适合用栈。很多人觉得栈题难是因为题目包装得很花哨。但 Hot 100 里的栈题本质上只围绕四件事打转括号匹配、配对消除靠栈的先进后出特性处理最近匹配。寻找下一个更大/更小的元素靠单调栈维护候选序列。表达式求值、字符串解码靠栈保存“现场”方便括号结束后恢复外层状态。设计类题目比如最小栈靠辅助栈或差值记录来满足时间复杂度约束。1.1 一个朴素的判断方法看到什么样的题该想到栈我在刷题时给自己总结过一个很粗糙的“信号词”清单。不需要背看到题目出现下面这些特征第一反应就该考虑栈题目特征对应解法方向嵌套结构、成对出现括号、XML、格式化文本栈配对遇到右半部分弹栈找右边/左边第一个比它大或比它小的元素单调栈表达式求值带括号、带符号优先级双栈或栈保存现场字符串按规则重复展开像3[a2[c]]数字栈 字符串栈撤销操作、回退历史、函数调用现场栈天然匹配“后进先出”递归写出后想改成非递归显式栈模拟调用栈比如20. 有效的括号就是最纯粹的“配对消除”题。左括号入栈右括号看栈顶是否匹配匹配就弹出不匹配直接返回 false最后栈必须是空的。这个解法不需要背理解“最近匹配”四个字就能自己推出来。1.2 Hot 100 栈题全景先看地图再动刀我不建议按题号顺序刷先按题型分组更高效。Hot 100 里常见的栈题可以分成这么几类题目核心考点为什么归到栈20 有效的括号括号配对最近匹配、成对消除155 最小栈栈设计辅助栈维护历史最值739 每日温度下一个更大元素单调栈经典模板42 接雨水宽度累计单调递减栈按层计算84 柱状图中最大的矩形边界扩展单调递增栈找左右矮柱394 字符串解码嵌套展开双栈模拟展开现场224 基本计算器表达式解析栈保存符号与临时结果看起来每道题差别很大但共同要回答的问题只有一个当前这个状态要不要留到后面再处理如果答案是肯定的栈就是最顺手的数据结构。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]; DequeInteger 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]i0 直接入栈i1 时温度 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]; DequeInteger 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]; } DequeInteger 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; DequeInteger 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压栈然后重置res0、sign1去处理括号内部遇到右括号括号内计算完的结果乘以上一层符号再加上之前保存的res。public int calculate(String s) { int res 0, sign 1, num 0; DequeInteger 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) { DequeInteger countStack new ArrayDeque(); DequeStringBuilder 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 { DequeInteger data new ArrayDeque(); DequeInteger 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 栈帧、回溯与显式栈的对应关系栈在递归和回溯里的位置经常被忽略。一个回溯算法的递归调用过程本质上是系统的调用栈在帮你保存“尝试到哪一步了”。每次进入递归系统压入一个栈帧保存当前局部变量返回时栈帧弹出又回到之前的状态。这就是“回溯”名字的由来。如果忘记递归写法你可以用显式栈模拟。比如二叉树前序遍历DequeTreeNode 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. 常见坑位与排查清单栈相关的题代码量不大但极容易在小细节上翻车。我把自己踩过和见过的坑整理成了一张排查表刷题时卡住了直接对照找原因。现象典型原因处理方式空栈调用 peek 或 pop 导致异常没有判空就直接取栈顶操作前先用isEmpty()判断或使用边界哨兵结果老是小一格或大一圈单调栈里存了值而不是下标涉及宽度、距离、区间时统一存下标接雨水和最大矩形总写反单调方向搞反84 找更矮边界用递增栈42 找更高边界用递减栈相等元素处理导致答案偏差弹不弹等于当前值的元素没想清楚84 用弹掉相等的42 用触发计算各自对应不同边界语义基本计算器最后一位丢失循环结束没处理累积的数字循环末尾统一res sign * num字符串解码里多个数字拼错相邻数字字符只取了单个拼接时k k * 10 (c - 0)溢出问题题目数值接近 int 上限差值或中间结果超范围用 long 存差值必要时用Integer.parseInt前先判断范围还有一些经验我可以直接分享第一刷栈题时手边放一张纸模拟栈的进出过程。尤其是单调栈画几轮比看十遍题解都有用。栈里每个元素什么时候入、什么时候出出栈时你拿到了什么信息这张图会告诉你所有答案。第二不要对“有效的括号”这类简单题掉以轻心。用它当热身可以迅速检测自己是否还习惯栈的基本操作。我在面试时见过有人会把右括号误写成入栈条件这种低级错误很致命。第三可以按这个顺序刷20 有效的括号 - 155 最小栈 - 739 每日温度 - 42 接雨水 - 84 柱状图中最大的矩形 - 394 字符串解码 - 224 基本计算器。每一步都比前一步节奏快到基本计算器时你会自然发现前面练的括号和现场保存能力全都在这里汇合了。栈这个专题是 Hot 100 里投入产出比很高的内容。题型套路固定边界坑就那几类被它折磨一两次之后后面再遇到“候选者很多新来的一个元素要清算旧元素”的场景你都会下意识想到单调栈再遇到“嵌套子问题需要保留外层状态”的场景你也会下意识想到用栈保存现场。如果现在正卡在某一题上别急着翻题解先把它归到我前面分好的类型里去想想这个状态适不适合栈再动手写。多数情况下你会发现自己已经能独立写出一大半了。
延伸阅读

更多相关文章

2026/11/19 13:22:41

VS Code集成通义灵码:AI编程助手安装配置与多语言实战指南

1. 项目动机与整体设计思路 1.1 为什么是 VS Code 加通义灵码 我最早接触 VS Code 还是好多年前,当时身边人把它当“高级记事本”用,装上插件之后才慢慢变成主力编辑器。这两年 AI 编程助手铺天盖地,从 GitHub Copilot 到各种国产助手&#…

2026/11/17 18:24:00

Model-Optimizer实战:搭建模型优化工作流与避坑指南

Model-Optimizer这个名字,算法圈子里的人应该不陌生。训练完一个模型只是第一步,真正让人头疼的是怎么把它塞进业务里跑得又快又稳,同时精度还不掉太多。我见过太多项目死在“训练精度97%,上线之后延迟超预算、显存爆掉”这个坎上…

2026/11/18 2:55:53

Madeira:macOS Apple Silicon上的x86-64二进制翻译运行时适配器

1. “Madeira”不是地名,而是x86-64 macOS兼容层的代号 你搜“Madeira”,第一反应可能是葡萄牙那个风景如画的海岛——但在这类技术语境下,它根本不是地理名词,而是一个正在 quietly 演进、却极少被中文社区系统梳理的底层兼容项目…

2026/11/19 13:19:25

特种维修工短剧报名入口与网上查询全攻略

特种维修工短剧报名入口与网上查询全攻略 实操考试心里没底怕挂科,这是很多准备考特种维修工短剧证书的学员最真实的写照。尤其是涉及到操作类的考试,比如电焊、高空作业等,很多考生一想到要面对真实的设备和环境,心里就打鼓。但别担心,网上查询相关信息…

2026/11/19 13:19:25

电工作业包含电焊吗 别踩坑报名指南全在这了

电工作业包含电焊吗 别踩坑报名指南全在这了 不知道去哪报名怕被中介坑?电工作业包含电焊吗?这是很多想考电工证、焊工证的朋友们最关心的问题。尤其在郑州,培训机构鱼龙混杂,很多人因为不了解报考流程,反而被坑了钱还拿不到证。今天就来给你讲清楚,电…

2026/11/19 13:19:25

电工证解挂值不值得考?许昌水利工程工人的真实经历

电工证解挂值不值得考?许昌水利工程工人的真实经历 电工证解挂不是小事,特别是像我这样急需特种作业证才能上岗找工作的打工族。上个月,我还在工地上被负责人拦住,说我的低压电工证状态异常,需要“解挂”才能继续工作,不然连入场资格都没有。这事让我意…

2026/11/19 13:19:25

神盾局特种工报名怕被坑?全国通用证书怎么选最靠谱

神盾局特种工报名怕被坑?全国通用证书怎么选最靠谱 不知道去哪报名怕被中介坑?你不是一个人。最近几个月,我接到了不下20个来自河南各地的电话,都是问怎么报考神盾局特种工证,怕被坑、怕交了钱拿不到证、怕证不是全国通用的。这些问题我都经历过,也帮…

2026/11/19 13:19:25

如何证明自己是特种工与德保县电工证补贴的区别

特种工怎么证明自己?学历不高也能考!含金量还在上升 你是不是也这样,手里有个电工证、焊工证,但一到公司报材料时,人家问你“怎么证明你是特种工?”搞得你心里没底,还怕报不了名?其实,别担心,这事儿有章可循,尤其是现在政策越来越清晰, 含金量…

2026/11/19 13:08:53

广州黄埔办电工证怎么报名怕被中介坑?这几点必须知道

广州黄埔办电工证怎么报名怕被中介坑?这几点必须知道 你是不是也在为“广州黄埔办电工证怎么报名”这个问题发愁?担心跑错地方、被中介坑、花冤枉钱?别急,这篇文章就是为你量身打造的避坑指南,从怎么报名到证书价值、薪资前景、报考材料、年审流程,全都…

2026/11/18 21:12:58

电工证考试口诉怎么准备值不值得考

电工证考试口诉怎么准备值不值得考 实操考试心里没底怕挂科,这是大多数准备考电工证的人心里最真实的感受。尤其是面对【电工证考试口诉】环节,很多人不知道该怎么准备,甚至担心自己说不好就被淘汰。其实,只要掌握方法, 值不值得考…

2026/11/18 21:55:23

桑植县考电工证千万别踩坑!报名全流程教你避坑

桑植县考电工证千万别踩坑!报名全流程教你避坑 你是不是也遇到过这种情况:想考个电工证,但不知道从哪儿下手,怕被中介坑,怕花冤枉钱,更怕考了证还不能用?别急,这正是你该看这篇文章的原因。在桑植县考电工证,确实有很多人被坑过,但只要你知道流程、…

2026/11/19 0:04:42

深圳电工证培训考场模拟考试题库:郑州报考避坑指南

深圳电工证培训考场模拟考试题库:郑州报考避坑指南 证书过期了不知道怎么复审延期,很多人在遇到这个问题的时候才意识到特种作业证的重要性。其实,不管是电工证、焊工证还是高处作业证,这些证书不仅是上岗的“通行证”,更是法律对安全操作的硬性要求。尤…

2026/11/19 0:04:42

天津电工证查询入口多少钱能报上名

天津电工证查询入口多少钱能报上名 学历不高怕报不上名?别急,天津电工证查询入口其实没你想的那么难。今天咱们就来聊聊,怎么用最低的门槛、最少的钱,把电工证拿下来,还能查得到、用得上。 电工证到底值不值?先搞清楚它的作用…

2026/11/18 12:37:05

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

在智慧养宠时代,基于视觉的宠物身份识别技术正逐步从实验室走向家庭应用。然而,与配合度高的人类不同,宠物是典型的“非合作生物识别对象”——它们不会主动配合摄像头调整姿态,更无法控制光照环境。实际应用中,我们常…

2026/11/18 1:15:04

SSM电子书店源码全解析:结构、原理、部署与排错实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

还想了解更多?直接咨询顾问

免费诊断 + 免费方案 + 透明报价。

全国咨询热线400-8866-253
免费获取方案
☎咨询二维码 ☎ ↑