3.2 单调栈

---

1. 单调栈简介

单调栈（Monotone Stack）：在栈「先进后出」规则的基础上，要求从 栈顶 到 栈底 的元素单调递增或单调递减。

• 单调递增栈：从栈顶到栈底元素单调递增
• 单调递减栈：从栈顶到栈底元素单调递减

1.1 单调递增栈

单调递增栈：每次新元素进栈时，如果它比栈顶元素小，直接入栈；如果比栈顶元素大或相等，就把栈顶及以上所有小于等于它的元素依次弹出，直到栈顶比它大或栈空，再将新元素入栈。

这样可以保证：栈从栈顶到栈底的元素是递增的，且每个元素左侧第一个比它大的元素都能被快速找到。

单调递增栈的操作流程：

• 当前元素 $x$，如果 $x$ < 栈顶元素，直接入栈。
• 否则，不断弹出栈顶小于等于 $x$ 的元素，直到栈顶比 $x$ 大或栈空，然后将 $x$ 入栈。

下面以数组 $[2, 7, 5, 4, 6, 3, 4, 2]$ 为例，演示「单调递增栈」的入栈与出栈过程：

• 数组：$[2, 7, 5, 4, 6, 3, 4, 2]$，从左到右依次遍历。

步骤	当前元素	操作	栈状态（左为栈底）	说明
1	2	2 入栈	[2]	2 左侧无更大元素
2	7	2 出栈，7 入栈	[7]	7 左侧无更大元素
3	5	5 入栈	[7, 5]	5 左侧第一个更大元素为 7
4	4	4 入栈	[7, 5, 4]	4 左侧第一个更大元素为 5
5	6	4 出栈，5 出栈，6 入栈	[7, 6]	6 左侧第一个更大元素为 7
6	3	3 入栈	[7, 6, 3]	3 左侧第一个更大元素为 6
7	4	3 出栈，4 入栈	[7, 6, 4]	4 左侧第一个更大元素为 6
8	2	2 入栈	[7, 6, 4, 2]	2 左侧第一个更大元素为 4

最终，栈中元素为 $[7, 6, 4, 2]$。从栈顶（右）到栈底（左）为 $2, 4, 6, 7$，满足递增，符合单调递增栈的定义。

以第 5 步为例，图示如下：

1.2 单调递减栈

单调递减栈：每次新元素进栈时，只有当它比栈顶元素大时才能直接入栈；如果小于或等于栈顶元素，则需要先将栈中所有大于等于当前元素的元素依次弹出，直到栈顶元素小于当前元素或栈为空，再将新元素入栈。

这样可以保证：栈中始终只保留比当前入栈元素小的值，并且从栈顶到栈底的元素是单调递减的。

单调递减栈的操作流程如下：

• 假设当前待入栈元素为 $x$，如果 $x$ > 栈顶元素，则直接入栈。
• 否则，从栈顶开始，依次弹出所有大于等于 $x$ 的元素，直到遇到一个小于 $x$ 的元素或栈为空，然后将 $x$ 入栈。

下面以数组 $[4, 3, 2, 5, 7, 4, 6, 8]$ 为例，演示「单调递减栈」的入栈与出栈过程：

• 数组：$[4, 3, 2, 5, 7, 4, 6, 8]$，从左到右依次遍历。

步骤	当前元素	操作	栈状态（左为栈底）	说明
1	4	4 入栈	[4]	4 左侧无更小元素
2	3	4 出栈，3 入栈	[3]	3 左侧无更小元素
3	2	3 出栈，2 入栈	[2]	2 左侧无更小元素
4	5	5 入栈	[2, 5]	5 左侧第一个更小元素为 2
5	7	7 入栈	[2, 5, 7]	7 左侧第一个更小元素为 5
6	4	7 出栈，5 出栈，4 入栈	[2, 4]	4 左侧第一个更小元素为 2
7	6	6 入栈	[2, 4, 6]	6 左侧第一个更小元素为 4
8	8	8 入栈	[2, 4, 6, 8]	8 左侧第一个更小元素为 6

最终，栈中元素为 $[2, 4, 6, 8]$。从栈顶（右）到栈底（左）为 $8, 6, 4, 2$，满足递减，符合单调递减栈的定义。

以第 6 步为例，图示如下：

2. 单调栈适用场景

单调栈常用于 $O(n)$ 时间复杂度内高效解决「最近更大/更小元素」类问题，主要包括以下四种典型场景：

• 查找左侧第一个比当前元素更大 / 更小的元素。
• 查找右侧第一个比当前元素更大 / 更小的元素。

具体解法如下：

2.1 查找左侧第一个比当前元素大的元素

• 从左到右遍历数组，维护单调递增栈（栈顶到栈底递增）：
  • 当前元素入栈时，栈顶元素即为其左侧第一个更大元素；
  • 若栈为空，则左侧不存在更大元素。

2.2 查找左侧第一个比当前元素小的元素

• 从左到右遍历数组，维护单调递减栈（栈顶到栈底递减）：
  • 当前元素入栈时，栈顶元素即为其左侧第一个更小元素；
  • 若栈为空，则左侧不存在更小元素。

2.3 查找右侧第一个比当前元素大的元素

• 从左到右遍历数组，维护单调递增栈：
  • 当前元素将栈中比自己小的元素弹出，被弹出的元素的右侧第一个更大元素即为当前元素；
  • 若某元素未被弹出，则右侧不存在更大元素。
• 或者，从右到左遍历，入栈时栈顶即为右侧第一个更大元素。

2.4 查找右侧第一个比当前元素小的元素

• 从左到右遍历数组，维护单调递减栈：
  • 当前元素将栈中比自己大的元素弹出，被弹出的元素的右侧第一个更小元素即为当前元素；
  • 若某元素未被弹出，则右侧不存在更小元素。
• 或者，从右到左遍历，入栈时栈顶即为右侧第一个更小元素。

上述四类问题可以归纳为以下通用规则：

• 查「更大」用单调递增栈，查「更小」用单调递减栈；
• 查「左侧」看元素入栈时的栈顶；
• 查「右侧」看元素出栈时触发它的当前元素；
• 遍历方向通常为从左到右（部分场景可从右到左）。

3. 单调栈模板

以从左到右遍历元素为例，介绍一下构造单调递增栈和单调递减栈的模板。

3.1 单调递增栈模板

def monotoneIncreasingStack(nums):
    stack = []
    left
    for i, num in enumerate(nums):
        while stack and num >= stack[-1]:
            stack.pop()
        if stack:
        
        stack.append(num)

3.2 单调递减栈模板

def monotoneDecreasingStack(nums):
    stack = []
    for num in nums:
        while stack and num <= stack[-1]:
            stack.pop()
        stack.append(num)

等号的去留（>= 或 >，<= 或 <）决定是否保留相等元素，按题意调整。

4. 单调栈的经典应用

4.1 经典例题：下一个更大元素 I

4.1.1 题目链接

• 0496. 下一个更大元素 I

4.1.2 题目大意

给定两个没有重复元素的数组 $nums1$ 和 $nums2$ ，其中 $nums1$ 是 $nums2$ 的子集。

要求：找出 $nums1$ 中每个元素在 $nums2$ 中的下一个比其大的值。

• $nums1$ 中数字 $x$ 的下一个更大元素是指：$x$ 在 $nums2$ 中对应位置的右边的第一个比 $x$ 大的元素。如果不存在，对应位置输出 $-1$。

4.1.3 解题思路

第一种思路是根据题意直接暴力求解。遍历 $nums1$ 中的每一个元素。对于 $nums1$ 的每一个元素 $nums1[i]$，再遍历一遍 $nums2$，查找 $nums2$ 中对应位置右边第一个比 $nums1[i]$ 大的元素。这种解法的时间复杂度是 $O(n^2)$。

第二种思路是使用单调递增栈。因为 $nums1$ 是 $nums2$ 的子集，所以我们可以先遍历一遍 $nums2$，并构造单调递增栈，求出 $nums2$ 中每个元素右侧下一个更大的元素。然后将其存储到哈希表中。然后再遍历一遍 $nums1$，从哈希表中取出对应结果，存放到答案数组中。这种解法的时间复杂度是 $O(n)$。具体做法如下：

• 使用数组 $res$ 存放答案。使用 $stack$ 表示单调递增栈。使用哈希表 $num\_map$ 用于存储 $nums2$ 中下一个比当前元素大的数值，映射关系为 当前元素值：下一个比当前元素大的数值。

• 遍历数组 $nums2$，对于当前元素：

  • 如果当前元素值较小，则直接让当前元素值入栈。
  • 如果当前元素值较大，则一直出栈，直到当前元素值小于栈顶元素。
    • 出栈时，出栈元素是第一个大于当前元素值的元素。则将其映射到 $num\_map$ 中。

• 遍历完数组 $nums2$，建立好所有元素下一个更大元素的映射关系之后，再遍历数组 $nums1$。

• 从 $num\_map$ 中取出对应的值，将其加入到答案数组中。

• 最终输出答案数组 $res$。

4.1.4 代码

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res = []
        stack = []
        num_map = dict()
        for num in nums2:
            while stack and num > stack[-1]:
                num_map[stack[-1]] = num
                stack.pop()
            stack.append(num)

        for num in nums1:
            res.append(num_map.get(num, -1))
        return res

4.2 每日温度

4.2.1 题目链接

• 739. 每日温度 - 力扣（LeetCode）

4.2.2 题目大意

描述：给定一个列表 $temperatures$，$temperatures[i]$ 表示第 $i$ 天的气温。

要求：输出一个列表，列表上每个位置代表「如果要观测到更高的气温，至少需要等待的天数」。如果之后的气温不再升高，则用 $0$ 来代替。

说明：

• $1 \le temperatures.length \le 10^5$。
• $30 \le temperatures[i] \le 100$。

示例：

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]


输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

4.2.3 解题思路

题目的意思实际上就是给定一个数组，每个位置上有整数值。对于每个位置，在该位置右侧找到第一个比当前元素更大的元素。求「该元素」与「右侧第一个比当前元素更大的元素」之间的距离，将所有距离保存为数组返回结果。

最简单的思路是对于每个温度值，向后依次进行搜索，找到比当前温度更高的值。

更好的方式使用「单调递增栈」，栈中保存元素的下标。

思路 1：单调栈

1. 首先，将答案数组 $ans$ 全部赋值为 0。然后遍历数组每个位置元素。
2. 如果栈为空，则将当前元素的下标入栈。
3. 如果栈不为空，且当前数字大于栈顶元素对应数字，则栈顶元素出栈，并计算下标差。
4. 此时当前元素就是栈顶元素的下一个更高值，将其下标差存入答案数组 $ans$ 中保存起来，判断栈顶元素。
5. 直到当前数字小于或等于栈顶元素，则停止出栈，将当前元素下标入栈。
6. 最后输出答案数组 $ans$。

思路 1：代码

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        n = len(T)
        stack = []
        ans = [0 for _ in range(n)]
        for i in range(n):
            while stack and T[i] > T[stack[-1]]:
                index = stack.pop()
                ans[index] = (i-index)
            stack.append(i)
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(n)$。

练习题目

• 0496. 下一个更大元素 I

• 0739. 每日温度

• 0316. 去除重复字母

• 单调栈题目列表

参考资料

• 【博文】动画：什么是单调栈？_- 吴师兄学编程
• 【博文】单调栈 - OI Wiki
• 【博文】单调栈解题模板秒杀八道题 - lucifer 的网络博客
• 【博文】理解单调栈与单调队列 - Hopefully Sky 的博客