一篇带你彻底学会单调栈文章目录一篇带你彻底学会单调栈前言例题一中等[739. 每日温度](https://leetcode.cn/problems/daily-temperatures/)- 单调栈- 图文解析例题二困难[84. 柱状图中最大的矩形](https://leetcode.cn/problems/largest-rectangle-in-histogram/)左右开弓双单调栈结语前言既然学习单调栈我们首先要知道什么是单调栈单调栈能用来做什么怎么实现单调栈其次什么时候用单调递增栈什么时候用单调递减栈什么是单调栈单调栈 栈 单调性约束。普通栈只遵循“后进先出”而单调栈在入栈时多加了一条规则新元素入栈前先把栈顶那些破坏单调性的元素弹出去从而保证栈内元素始终单调。这里统一约定单调性看的是从栈底到栈顶的变化方向。递增栈栈底到栈顶逐渐变大栈底最小栈顶最大递减栈栈底到栈顶逐渐变小栈底最大栈顶最小注也有资料按从栈顶到栈底来命名方向恰好相反。本文统一按栈底→栈顶来记避免混淆。单调栈的实现以递增栈为例核心代码只有四行DequeIntegerstacknewArrayDeque();for(inti0;in;i){while(!stack.isEmpty()heights[stack.peek()]heights[i]){stack.pop();// 弹出破坏单调性的栈顶}stack.push(i);// 当前元素入栈}关键点栈里存下标不存值。因为大多数题目要算距离、求宽度存下标才方便。弹栈条件决定了单调性。 弹出 → 递增栈 弹出 → 递减栈。相等时弹不弹取决于题目要求。求严格小于就弹等号求小于等于就保留等号这个细节后面单独讲。单调栈能做什么一句话求每个元素左边/右边第一个比它大或小的元素。这是单调栈最核心、最通用的使用场景。所有变形题接雨水、柱状图最大矩形、每日温度等本质都是它的包装。为什么能做到 O(n)因为每个元素最多进栈一次、出栈一次总操作次数是 2n所以整体是线性的。两种单调栈怎么选记住这个口诀找小递增找大递减。目标用哪种栈弹出时机的含义找右边第一个比它小的元素递增栈当前元素比栈顶小 → 栈顶找到了答案找右边第一个比它大的元素递减栈当前元素比栈顶大 → 栈顶找到了答案记忆逻辑比死记硬背更靠谱我们要找右边第一个更小的那么栈里保持递增——因为递增栈的栈顶是当前最大的一旦遇到比它小的新元素就说明栈顶找到了答案。反之找右边第一个更大的栈里保持递减栈顶是当前最小的遇到比它大的新元素就弹出。例题一中等739. 每日温度给定一个整数数组temperatures表示每天的温度返回一个数组answer其中answer[i]是指对于第i天下一个更高温度出现在几天后。如果气温在这之后都不会升高请在该位置用0来代替。示例 1:输入: temperatures [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]示例 2:输入: temperatures [30,40,50,60] 输出: [1,1,1,0]示例 3:输入: temperatures [30,60,90] 输出: [1,1,0]- 单调栈我们维护一个单调递减栈这个单调递减栈的操作是这样的第一种情况是栈为空或者当前温度小于等于栈顶温度这符合递减栈的规则所以直接将当前下标入栈。第二种情况是当前温度大于栈顶温度这说明栈顶元素已经找到了它需要的更高温度于是进入内层循环只要栈不为空且当前温度继续大于栈顶温度就反复计算天数差并写入数组同时将栈顶弹出。内层循环结束后当前温度也要作为新的栈顶元素入栈以便后续比较。当整个数组遍历完成后栈中可能还会剩余一些下标这些下标对应的日子再也没有遇到更高的温度根据题目要求需要将它们对应的位置赋值为零。最后返回这个被修改过的数组就是最终答案- 图文解析Golang代码解析funcdailyTemperatures(temperatures[]int)[]int{//单调栈stack:[]int{}fori,v:rangetemperatures{//当前元素大于栈顶元素的时候弹出直到符合单调栈的情况forlen(stack)!0vtemperatures[stack[len(stack)-1]]{temperatures[stack[len(stack)-1]]i-stack[len(stack)-1]stackstack[:len(stack)-1]}//对当前元素入栈stackappend(stack,i)}//剩余的元素也要出栈对于剩余的元素把结果直接记录为0for_,v:rangestack{temperatures[v]0stackstack[:len(stack)-1]}returntemperatures}Java代码解析importjava.util.Deque;importjava.util.ArrayDeque;importjava.util.Arrays;classSolution{publicint[]dailyTemperatures(int[]temperatures){intntemperatures.length;int[]answernewint[n];// 单调递减栈存下标DequeIntegerstacknewArrayDeque();for(inti0;in;i){// 当前温度大于栈顶对应的温度说明找到了更高温度while(!stack.isEmpty()temperatures[i]temperatures[stack.peek()]){intprevIndexstack.pop();answer[prevIndex]i-prevIndex;}stack.push(i);}// 栈中剩余的下标后面没有更高温度answer 默认为 0returnanswer;}}例题二困难84. 柱状图中最大的矩形给定n个非负整数用来表示柱状图中各个柱子的高度。每个柱子彼此相邻且宽度为 1 。求在该柱状图中能够勾勒出来的矩形的最大面积。示例 1:输入heights [2,1,5,6,2,3] 输出10 解释最大的矩形为图中红色区域面积为 10示例 2输入 heights [2,4] 输出 4左右开弓双单调栈这道题是上一道题的升级版。 看起来复杂其实核心就是维护两个单调栈一个记录每个元素左边第一个比它小的位置另一个记录右边第一个比它小的位置。这两个边界之间的所有柱子就是当前柱子能扩展出的矩形范围不包含这两个更矮的边界。那为什么要设计这样的数学公式为什么向左右扩展时一遇到比当前元素小的值就停下 如果不想清楚这一点就很难迈出第一步更不会想到要用单调栈。原理其实很简单如果没有边界限制所有位置向左右扩展最后都会变成同一个矩形——高是数组里的最小值宽是整个数组的长度。那这个矩形显然不一定是最优解。那为什么停在“比当前元素小”的边界处就没问题会不会漏掉某种组合我们遍历时如果每次都尽量选择高度大于等于自己的柱子矩形面积就有机会持续变大而一旦选择了小于自己高度的柱子矩形的高就会被拉低面积可能变小。但“可能变小”不代表“一定变小”这里容易产生一个疑问比如数组是 6, 5, 4那高度为 6 的柱子不去兼容更小的 5 和 4岂不是错过了更大的矩形事实上不会漏——因为遍历到 5 的时候它会自动向左扩展把 6 包进来遍历到 4 的时候又会继续向左扩展把 6、5 都包进来。这样以 5 为高的最大矩形、以 4 为高的最大矩形都会在各自的遍历中被算到。所以设计时必须遵从同一套逻辑只向“大于等于自己”的方向扩展。 如果既扩展高的、又扩展低的逻辑就会非常混乱而且本质上就退化成了暴力解法时间复杂度 O(n²)。下面基于单调栈写代码。Java代码解析classSolution{publicintlargestRectangleArea(int[]heights){intnheights.length;int[]leftnewint[n];int[]rightnewint[n];DequeIntegermono_stacknewArrayDequeInteger();for(inti0;in;i){while(!mono_stack.isEmpty()heights[mono_stack.peek()]heights[i]){mono_stack.pop();}left[i](mono_stack.isEmpty()?-1:mono_stack.peek());mono_stack.push(i);}mono_stack.clear();for(intin-1;i0;--i){while(!mono_stack.isEmpty()heights[mono_stack.peek()]heights[i]){mono_stack.pop();}right[i](mono_stack.isEmpty()?n:mono_stack.peek());mono_stack.push(i);}intans0;for(inti0;in;i){ansMath.max(ans,(right[i]-left[i]-1)*heights[i]);}returnans;}}作者力扣官方题解 链接https://leetcode.cn/problems/largest-rectangle-in-histogram/solutions/266844/zhu-zhuang-tu-zhong-zui-da-de-ju-xing-by-leetcode-/来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。Golang代码解析funclargestRectangleArea(heights[]int)int{n:len(heights)left,right:make([]int,n),make([]int,n)mono_stack:[]int{}fori:0;in;i{forlen(mono_stack)0heights[mono_stack[len(mono_stack)-1]]heights[i]{mono_stackmono_stack[:len(mono_stack)-1]}iflen(mono_stack)0{left[i]-1}else{left[i]mono_stack[len(mono_stack)-1]}mono_stackappend(mono_stack,i)}mono_stack[]int{}fori:n-1;i0;i--{forlen(mono_stack)0heights[mono_stack[len(mono_stack)-1]]heights[i]{mono_stackmono_stack[:len(mono_stack)-1]}iflen(mono_stack)0{right[i]n}else{right[i]mono_stack[len(mono_stack)-1]}mono_stackappend(mono_stack,i)}ans:0fori:0;in;i{ansmax(ans,(right[i]-left[i]-1)*heights[i])}returnans}funcmax(x,yint)int{ifxy{returnx}returny}作者力扣官方题解 链接https://leetcode.cn/problems/largest-rectangle-in-histogram/solutions/266844/zhu-zhuang-tu-zhong-zui-da-de-ju-xing-by-leetcode-/来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。结语这两道题其实是一回事每日温度找的是“右边第一个比自己大的”柱状图找的是“左右第一个比自己小的”一个找大一个找小一个用递减栈一个用递增栈但底层动作完全相同——都是在元素进栈出栈的瞬间替它确定那条决定命运的边界。所谓单调栈说到底就是把“找边界”这件事从暴力枚举的 O(n²) 压缩成一次遍历的 O(n)。理解了边界从哪来、为什么停在那里模板就不再需要背了。**本文是 《算法题目解析系列》 的第 [31] 篇本系列将持续更新每篇都提供清晰的思路与编程语言实现。如果你有想看的题目也可以在评论区留言告诉我码字不易如果觉得这篇文章对您有帮助希望可以点点赞或者关注我以便于第一时间获取更新。