算法题还不会写单调栈？一篇单调栈超详解+例题解析给你保姆级教学！

一篇带你彻底学会单调栈

前言：

既然学习单调栈，我们首先要知道什么是单调栈？单调栈能用来做什么？怎么实现单调栈？其次，什么时候用单调递增栈？什么时候用单调递减栈？

1. 什么是单调栈？

• 单调栈 = 栈 + 单调性约束。

• 普通栈只遵循“后进先出”，而单调栈在入栈时多加了一条规则：新元素入栈前，先把栈顶那些"破坏单调性"的元素弹出去，从而保证栈内元素始终单调。

• 这里统一约定：单调性看的是从栈底到栈顶的变化方向。

• 递增栈：栈底到栈顶逐渐变大（栈底最小，栈顶最大）

• 递减栈：栈底到栈顶逐渐变小（栈底最大，栈顶最小）

注：也有资料按"从栈顶到栈底"来命名，方向恰好相反。本文统一按"栈底→栈顶"来记，避免混淆。

2. 单调栈的实现

• 以递增栈为例，核心代码只有四行：

Deque<Integer>stack=newArrayDeque<>();for(inti=0;i<n;i++){while(!stack.isEmpty()&&heights[stack.peek()]>=heights[i]){stack.pop();// 弹出破坏单调性的栈顶}stack.push(i);// 当前元素入栈}

• 关键点：

• 栈里存下标，不存值。因为大多数题目要算距离、求宽度，存下标才方便。

• 弹栈条件决定了单调性。>= 弹出 → 递增栈；<= 弹出 → 递减栈。

• 相等时弹不弹，取决于题目要求。求"严格小于"就弹等号，求"小于等于"就保留等号，这个细节后面单独讲。

3. 单调栈能做什么？

• 一句话：求每个元素左边/右边第一个比它大（或小）的元素。

• 这是单调栈最核心、最通用的使用场景。所有变形题（接雨水、柱状图最大矩形、每日温度等）本质都是它的包装。

为什么能做到 O(n)？
因为每个元素最多进栈一次、出栈一次，总操作次数是 2n，所以整体是线性的。

4. 两种单调栈怎么选？

• 记住这个口诀：

• 找小递增，找大递减。

• 记忆逻辑（比死记硬背更靠谱）：

• 我们要找"右边第一个更小的"，那么栈里保持递增——因为递增栈的栈顶是当前最大的，一旦遇到比它小的新元素，就说明栈顶找到了答案。

• 反之找"右边第一个更大的"，栈里保持递减，栈顶是当前最小的，遇到比它大的新元素就弹出。

例题一（中等）：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)!=0&&v>temperatures[stack[len(stack)-1]]{temperatures[stack[len(stack)-1]]=i-stack[len(stack)-1]stack=stack[:len(stack)-1]}//对当前元素入栈stack=append(stack,i)}//剩余的元素也要出栈，对于剩余的元素把结果直接记录为0for_,v:=rangestack{temperatures[v]=0stack=stack[:len(stack)-1]}returntemperatures}

Java代码解析

importjava.util.Deque;importjava.util.ArrayDeque;importjava.util.Arrays;classSolution{publicint[]dailyTemperatures(int[]temperatures){intn=temperatures.length;int[]answer=newint[n];// 单调递减栈，存下标Deque<Integer>stack=newArrayDeque<>();for(inti=0;i<n;i++){// 当前温度大于栈顶对应的温度，说明找到了更高温度while(!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){intprevIndex=stack.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

左右开弓！双单调栈

1. 这道题是上一道题的升级版。 看起来复杂，其实核心就是维护两个单调栈：一个记录每个元素左边第一个比它小的位置，另一个记录右边第一个比它小的位置。这两个边界之间的所有柱子，就是当前柱子能扩展出的矩形范围（不包含这两个更矮的边界）。

2. 那为什么要设计这样的数学公式？为什么向左右扩展时，一遇到比当前元素小的值就停下？ 如果不想清楚这一点，就很难迈出第一步，更不会想到要用单调栈。原理其实很简单：如果没有边界限制，所有位置向左右扩展，最后都会变成同一个矩形——高是数组里的最小值，宽是整个数组的长度。那这个矩形显然不一定是最优解。

3. 那为什么停在“比当前元素小”的边界处就没问题？会不会漏掉某种组合？我们遍历时，如果每次都尽量选择高度大于等于自己的柱子，矩形面积就有机会持续变大；而一旦选择了小于自己高度的柱子，矩形的高就会被拉低，面积可能变小。但“可能变小”不代表“一定变小”，这里容易产生一个疑问：比如数组是 6, 5, 4，那高度为 6 的柱子不去兼容更小的 5 和 4，岂不是错过了更大的矩形？事实上不会漏——因为遍历到 5 的时候，它会自动向左扩展（把 6 包进来）；遍历到 4 的时候，又会继续向左扩展（把 6、5 都包进来）。这样，以 5 为高的最大矩形、以 4 为高的最大矩形，都会在各自的遍历中被算到。

4. 所以设计时必须遵从同一套逻辑：只向“大于等于自己”的方向扩展。 如果既扩展高的、又扩展低的，逻辑就会非常混乱，而且本质上就退化成了暴力解法，时间复杂度 O(n²)。下面基于单调栈写代码。

Java代码解析

classSolution{publicintlargestRectangleArea(int[]heights){intn=heights.length;int[]left=newint[n];int[]right=newint[n];Deque<Integer>mono_stack=newArrayDeque<Integer>();for(inti=0;i<n;++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(inti=n-1;i>=0;--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);}intans=0;for(inti=0;i<n;++i){ans=Math.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;i<n;i++{forlen(mono_stack)>0&&heights[mono_stack[len(mono_stack)-1]]>=heights[i]{mono_stack=mono_stack[:len(mono_stack)-1]}iflen(mono_stack)==0{left[i]=-1}else{left[i]=mono_stack[len(mono_stack)-1]}mono_stack=append(mono_stack,i)}mono_stack=[]int{}fori:=n-1;i>=0;i--{forlen(mono_stack)>0&&heights[mono_stack[len(mono_stack)-1]]>=heights[i]{mono_stack=mono_stack[:len(mono_stack)-1]}iflen(mono_stack)==0{right[i]=n}else{right[i]=mono_stack[len(mono_stack)-1]}mono_stack=append(mono_stack,i)}ans:=0fori:=0;i<n;i++{ans=max(ans,(right[i]-left[i]-1)*heights[i])}returnans}funcmax(x,yint)int{ifx>y{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] 篇，本系列将持续更新，每篇都提供清晰的思路与编程语言实现。如果你有想看的题目，也可以在评论区留言告诉我，码字不易，如果觉得这篇文章对您有帮助，希望可以点点赞，或者关注我，以便于第一时间获取更新。