文章目录前言一、LC 155 最小栈题目思路代码二、LC 394 字符串解码题目思路代码三、LC 739 每日温度题目思路代码四、LC 84 柱状图中最大的矩形题目思路宽度公式为什么是 i - left - 1哨兵技巧代码五、栈专题总结前言这篇文章用四道 LeetCode 经典题把「栈」这个数据结构从基础用法讲到单调栈的进阶套路读完你能建立起一条清晰的解题主线什么时候该用栈、普通栈和单调栈的区别、以及单调栈那个总也记不住的宽度公式到底怎么来的。栈的核心就一句话后进先出。但真正难的不是这个结构而是识别「这道题为什么要用栈」。很多题目表面看不出来但只要出现「最近一次」「最近一个更大/更小」「括号/嵌套匹配」这类字眼栈往往就是答案。四道题按难度递进LC 155 最小栈栈的基础设计题学会「用辅助信息扩展栈」LC 394 字符串解码嵌套结构学会「用栈处理括号匹配」LC 739 每日温度单调栈入门学会「找右边第一个更大」LC 84 柱状图最大矩形单调栈进阶学会「宽度边界的推导」一、LC 155 最小栈题目设计一个栈支持push、pop、top并且能在O(1)时间内取到栈里的最小值。思路难点在「O(1) 取最小值」。如果每次遍历找最小那是 O(n)不达标。核心技巧用一个辅助栈同步记录「当前状态下的最小值」。主栈存真实数据辅助栈的栈顶永远是主栈当前所有元素的最小值。两个栈同步进出最小值随手可取。push 3 push 5 push 2 主栈: [3] 主栈: [3,5] 主栈: [3,5,2] 辅栈: [3] 辅栈: [3,3] 辅栈: [3,3,2] ↑ ↑ 53不更新 23更新最小弹出时两个栈一起弹辅助栈栈顶自然回退到上一个最小值。代码classMinStack{DequeIntegerstack;// 主栈存真实数据DequeIntegerminStack;// 辅助栈栈顶当前最小值publicMinStack(){stacknewArrayDeque();minStacknewArrayDeque();}publicvoidpush(intval){stack.push(val);// 辅助栈存「当前和历史最小值中的较小者」if(minStack.isEmpty())minStack.push(val);elseminStack.push(Math.min(val,minStack.peek()));}publicvoidpop(){stack.pop();minStack.pop();// 同步弹出}publicinttop(){returnstack.peek();}publicintgetMin(){returnminStack.peek();// O(1) 取最小}}关键点辅助栈每个位置存的不是「新压入的值」而是「压入这个值之后栈里的最小值」。这样弹栈时最小值能正确回退。时间所有操作 O(1)。空间O(n)多用一个辅助栈。二、LC 394 字符串解码题目给一个编码字符串3[a]解码成aaa3[a2[c]]解码成accaccacc。括号可以嵌套。思路嵌套结构天然适合栈。难点在于遇到]时要知道「重复几次」和「重复什么」。用双栈一个存数字重复次数一个存进入括号前已经拼好的字符串。遇到数字累积成完整的倍数可能多位比如12[a]遇到[把当前倍数和当前字符串压栈然后清零进入新一层遇到]弹出倍数和上层字符串把当前层重复拼接后接到上层后面遇到字母直接接到当前字符串输入 3[a2[c]] 遇到 3 num3 遇到 [ 压栈 num3, str 当前 str 遇到 a stra 遇到 2 num2 遇到 [ 压栈 num2, stra 当前 str 遇到 c strc 遇到 ] 弹出2和aaccacc当前 stracc 遇到 ] 弹出3和, acc×3accaccacc代码classSolution{publicStringdecodeString(Strings){DequeIntegernumStacknewArrayDeque();// 存重复次数DequeStringBuilderstrStacknewArrayDeque();// 存上层字符串StringBuildercurnewStringBuilder();intnum0;for(charc:s.toCharArray()){if(c0c9){numnum*10(c-0);// 处理多位数字}elseif(c[){numStack.push(num);strStack.push(cur);num0;curnewStringBuilder();// 进入新一层}elseif(c]){intknumStack.pop();StringBuildertmpstrStack.pop();for(inti0;ik;i)tmp.append(cur);// 重复拼接curtmp;// 回到上层}else{cur.append(c);}}returncur.toString();}}易错点数字要用num num*10 (c-0)累积别以为倍数只有一位。100[a]是合法输入。时间 O(n × maxK)maxK 是最大重复倍数。空间 O(n)。补充这题也能用递归写。但记住一个 Java 性能坑——循环里拼字符串千万别用String 那是 O(n²)。String 不可变每次都要把已有内容整个复制一遍。一定要用StringBuilder它内部是可变数组append直接往尾部填整体 O(n)。三、LC 739 每日温度题目给一个温度数组对每一天求「还要等几天才能遇到更高的温度」。没有更高的填 0。比如[73,74,75,71,69,72,76,73]→[1,1,4,2,1,1,0,0]。思路这是单调栈的入门题。问题本质是对每个元素找右边第一个比它大的元素在哪。暴力对每天向右扫是 O(n²)。单调栈能 O(n) 搞定。维护一个递减栈存下标对应温度从栈底到栈顶递减。遍历时当前温度 ≤ 栈顶温度直接入栈保持递减当前温度 栈顶温度说明找到了栈顶那天的「下一个更高温」弹出并计算天数差一直弹到不满足为止温度 [73, 74, 75, 71, 69, 72, 76] i0 温度73 栈空压入 栈:[0] i1 温度74 73弹0算差1 栈:[1] ans[0]1-01 i2 温度75 74弹1算差1 栈:[2] ans[1]2-11 i3 温度71 75压入 栈:[2,3] i4 温度69 71压入 栈:[2,3,4] i5 温度72 69弹4,71弹3 栈:[2,5] ans[4]1, ans[3]2 i6 温度76 72弹5,75弹2 栈:[6] ans[5]1, ans[2]4代码classSolution{publicint[]dailyTemperatures(int[]t){intnt.length;int[]ansnewint[n];DequeIntegerstacknewArrayDeque();// 存下标温度递减for(inti0;in;i){// 当前温度比栈顶高栈顶那天的答案就是 i - 栈顶下标while(!stack.isEmpty()t[i]t[stack.peek()]){intidxstack.pop();ans[idx]i-idx;}stack.push(i);}returnans;// 栈里剩下的天没有更高温默认 0}}单调栈的信号题目问「下一个更大/更小」「最近一个更大/更小」几乎都是单调栈。栈里存下标而不是值这样能算距离。时间 O(n)每个元素进出栈各一次。空间 O(n)。四、LC 84 柱状图中最大的矩形题目给一组柱子的高度求能勾勒出的最大矩形面积。__ | |__ __| | | | | | |__ | | | | | ---------------- 2 4 3 1思路这是单调栈的进阶题也是最容易在「宽度公式」上翻车的题。对每根柱子想以它的高度作为矩形的高能向左右扩展多宽答案是向左找到第一根比它矮的向右找到第一根比它矮的这两个边界之间就是最大宽度。这又回到「找左右第一个更小」正是单调栈的强项。维护递增栈存下标当遇到比栈顶矮的柱子时栈顶的右边界就找到了。结算柱子 cur 时 右边界 i 当前这根第一个比 cur 矮的 左边界 弹出 cur 后的新栈顶 cur 左边第一个比它矮的 宽度 i - left - 1 左右边界之间不含边界 面积 height[cur] × 宽度宽度公式为什么是 i - left - 1这是最关键、也最容易错的地方。很多人会写成i - cur或i - cur - 1都是错的。宽度不是「当前位置减柱子位置」而是「左右两个边界之间能站多少根柱子」。举例高度(加哨兵): [0, 2, 1, 5, 6, 2, 0] 下标: 0 1 2 3 4 5 6遍历到i5高度2结算cur4高度6弹出 cur4 后新栈顶 left3高度5 宽度 i - left - 1 5 - 3 - 1 1高度6只能自己站一根左边5矮、右边2矮宽度1正确。继续结算cur3高度5弹出 cur3 后新栈顶 left2高度1 宽度 i - left - 1 5 - 2 - 1 2高度5能覆盖下标3和4两根宽度2正确。如果用错误的i - cur结算高度5时会算成5 - 3 2碰巧对但结算别的柱子时就会偏大。核心原因是i - cur完全忽略了左边界只有当左边界恰好紧挨着 cur 时才碰巧正确。哨兵技巧首尾各加一个高度 0 的哨兵头部哨兵 height[0]0 永远在栈底保证结算时栈不空充当左边界兜底 尾部哨兵 height[n1]0遍历到它时把栈里剩下的柱子全部弹出结算没有哨兵就要额外写「空栈判断」和「遍历结束后清算剩余栈」两段代码哨兵把这两个边界情况一次性抹平。代码classSolution{publicintlargestRectangleArea(int[]heights){intnheights.length,ans0;int[]heightnewint[n2];// 首尾加哨兵for(inti0;in;i)height[i1]heights[i];DequeIntegerstacknewArrayDeque();// 存下标高度递增for(inti0;iheight.length;i){while(!stack.isEmpty()height[i]height[stack.peek()]){intcurstack.pop();intleftstack.peek();// 新栈顶 左边界intwidthi-left-1;// 关键公式ansMath.max(ans,height[cur]*width);}stack.push(i);}returnans;}}时间 O(n)空间 O(n)。五、栈专题总结把四道题的解题信号串起来题目特征 用什么 核心技巧 ------------------------------------------------------------ O(1) 取最值 栈 辅助栈 同步记录当前最值 括号/嵌套结构 栈可双栈 遇[压栈, 遇]弹栈拼接 下一个更大/更小、最近更大/更小 单调栈 存下标算距离 向左右扩展找边界 单调栈 哨兵 宽度 i - left - 1几条通用经验栈里存下标不存值。存下标既能拿到值arr[idx]又能算距离信息更全。单调栈的方向找更大用递减栈找更小用递增栈栈内从底到顶的单调性和你要找的方向相反。哨兵能消灭边界判断。首尾补 0 或补极值让空栈处理和收尾清算统一进主循环。宽度公式记死i - left - 1左右边界之间不含边界。不要用i - cur。Java 拼字符串用 StringBuilder循环里String 是 O(n²) 陷阱。单调栈的难点从来不是代码而是想清楚「我到底在找每个元素的什么边界」。把这个想明白剩下的就是套模板。下一篇队列与单调队列——从 LC 239 滑动窗口最大值说起