单调栈的概念

单调栈指的是维护一个栈，栈内的元素从栈顶到栈底维持递增或者递减的顺序。

以递增栈为例，看看单调栈的维护过程————当遍历元素小于栈顶元素时，此时没有破坏单调栈的单调递增关系，将遍历元素入栈（有时候等于也要入栈，看解题的具体需要）；当遍历元素大于栈顶元素时，此时破坏了单调栈的单调递增关系，就需要进行一系列的操作（可能是记录答案），将栈顶元素出栈，继续将遍历元素与栈顶元素比较，直到小于（等于）栈顶元素，或者栈为空，不再破坏单调栈的单调递增关系，此时才可以将遍历元素入栈。

单调栈的适用场景是找数组中左边第一个最大/最小数、右边第一个最大/最小数。为什么单调栈适合于数组中左边最大/最小的第一个数、右边最大/最小第一个数？以递增栈寻找数组右边第一个最大的数为例子，

  1. 单调栈的栈，作为栈用来存放遍历过的、还没找到答案的元素，对于找到答案的元素，就不会再存在于栈内，它们都会被弹出；

  2. 单调栈的单调，单调，保证了在当前的遍历流程中，栈顶元素还没有遇到右边比它大的元素，虽然存在于栈内的元素都是比栈顶元素大的，但是它们都先于栈顶元素加入栈中，按照遍历顺序，它们在数组中的位置是处于栈顶元素左边的；

  3. 单调栈在填写答案的时候通常是乱序的，和正常暴力的手段相比特别不直观，所以比较难理解，也会觉得单调栈很妙。要多画图进行模拟才能彻底搞清楚单调栈的运行过程。

739.每日温度

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

暴力解法

最容易想到的就是双指针暴力解法，两层for循环直接往后搜索第一个更高温度，时间复杂度是O(n^2)。但是会超时哈哈，遇到重复温度很多、数组很长的时候特别慢。

1
2
3
4
5
6
7
8
9
10
11
12
func dailyTemperatures(temperatures []int) []int {
	res := make([]int, len(temperatures))
	for i := 0; i < len(temperatures); i++ {
		for j := i + 1; j < len(temperatures); j++ {
			if temperatures[j] > temperatures[i] {
				res[i] = j - i
				break
			}
		}
	}
	return res
}

优化暴力

暴力解法容易超时，原因在于它得遍历几乎整个数组。就拿数组中的元素来说，当我们针对元素 i 去寻找它右边第一个更高温度时，需要遍历后面的元素。可等要找元素 i + 1 右边第一个更高温度时，又得重新遍历后面的元素，这样就出现了大量重复计算的情况。

那有什么办法可以减少重复计算呢？答案是用空间换时间，进行预处理，提前准备好每个元素右边第一次出现更高温度的位置信息，这样后面找的时候就不用每次都重新找一遍。那么如何准备更高温度的位置信息呢？因为需要提前准备右边更高温度的位置信息，所以预处理就需要从右往左进行，不断更新高温的第一次出现的位置信息。

具体如何准备呢？我们使用一个next数组，next数组存储已遍历的元素第一次在数组中出现的下标，next数组的长度是所有的温度，即 101 。注意这里的第一次，是针对已经遍历过的元素而言，从左往右元素第一次出现的位置。举个例子，对[4,5,5,5,6]，当 i == 1 时，next[5] = 2 ，因为针对的是在[5,5,6]中从左往右第一次出现 5 的位置。

next数组准备就绪了，我们就可以根据next数组去找寻答案了。对于当前的元素，需要寻找右边第一次出现更高温度的位置，在next数组中暴力查询，查询所有更大元素第一次出现的下标，比较所有下标，得到的最小下标就是当前元素的答案。

具体流程如下：

  1. 初始化 next 数组长度为 101 ，所有元素为无穷大，用于后续更新下标；初始化答案数组res，长度为len(temperatures)

  2. 倒序遍历 temperatures 数组，对每个 temperatures[i] ，先初始化 warmerIndex 为无穷大，在 next 数组中从 temperatures[i]+1 开始到 100 搜索所有更高温度的下标，并使用变量 warmerIndex 记录最小的下标。在遍历完 next 数组后，warmerIndex不为无穷大则表示找到更高温，填写res；否则没找到答案，不写res。

  3. 更新next数组，next[temperatures[i]] = i

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 优化暴力：逆序遍历，使用next数组记录每个温度第一次出现的下标，初始化为无穷大
// 在逆序遍历过程中不断更新对已经遍历的温度来说，当前温度第一次出现的index
// 对于i，直接去next数组中遍历temperatures[i]+1到100，找每个更高温度出现的下标，求最小来计算差值
// 这种做法的合理性在于不断维护next数组，确保对一个数可以快速找到更高温度在其之后第一次出现的index
// 通过比较更高温度第一次出现的下标来确定index
func dailyTemperatures(temperatures []int) []int {
    res := make ([]int, len(temperatures))
    next := make([]int, 101)
    //初始化next元素为无穷大，方便后续更新
    for i:=0 ;i<101; i++ {
        next[i] = math.MaxInt
    }
    for i := len(temperatures)-1; i >= 0 ;i-- {
        t := temperatures[i]
        warmerIndex := math.MaxInt
        for j := t + 1; j < 101; j++ {
            if next[j] != math.MaxInt{
                warmerIndex = min(warmerIndex, next[j])
            }
        }
        if warmerIndex != math.MaxInt{
            res[i] = warmerIndex - i
        }
        next[t] = i 
    }
    return res
}

单调栈

使用栈顶到栈底递增的单调栈来实现。因为本题的最终答案是下标差，不是简单的更高温度是多少，所以栈内需要存放下标，同时可以通过下标快速找到温度进行温度比较。

使用单调栈的三个判断条件：

遍历元素T[i]大于栈顶元素T[st[len(st)-1]]：弹出栈顶元素，填写栈顶元素答案
遍历元素T[i]等于栈顶元素T[st[len(st)-1]]：入栈（我们需要填写每一个元素的答案，它们都还没遇到右边第一个更大的元素）
遍历元素T[i]小于栈顶元素T[st[len(st)-1]]：入栈

对于上述的判断条件，通过一次模拟就能够看懂整个流程，弄懂为什么这么做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 单调栈：适合于寻找左/右边第一个大/小的元素，维持栈内单调顺序
// 本题栈内存放下标，方便记录结果和比较温度大小
// 维持栈顶到栈底非严格递增顺序，栈内维持已经遍历过的元素的递增顺序，每次填写栈顶元素的结果
// 从头到尾遍历数组元素，对每个元素与栈顶元素比较大小进行操作，三种情况：大 等 小
// 大：破坏了栈内递增顺序，说明栈顶元素遇到了它右边最大的第一个元素，出栈并记录结果
// 小、等：维持栈内非严格递增顺序，直接入栈
// 精髓在于维持栈的单调顺序，每次填写栈顶元素结果，
// 栈的有序性确保栈顶元素根据当前遍历到的更大的元素找到右边最大的第一个数
func dailyTemperatures(temperatures []int) []int {
    res := make ([]int, len(temperatures))
    stack := make([]int, 0)
    stack = append(stack, 0)
    for i := 1; i < len(temperatures); i++ {
        if temperatures[i] <= temperatures[stack[len(stack)-1]] {
            stack = append(stack, i)
        }else if temperatures[i] == temperatures[stack[len(stack)-1]]{
            stack = append(stack, i)
        }else {
            for len(stack) != 0 && temperatures[i] > temperatures[stack[len(stack)-1]] {
                top := stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                res[top] = i - top
            } 
            stack = append(stack, i)
        }
    }  
    return res
}

发现了吧，上述stack = append(stack, i)可提取出来，精简代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 单调栈：适合于寻找左/右边第一个大/小的元素，维持栈内单调顺序
// 本题栈内存放下标，方便记录结果和比较温度大小
// 维持栈顶到栈底非严格递增顺序，栈内维持已经遍历过的元素的递增顺序，每次填写栈顶元素的结果
// 从头到尾遍历数组元素，对每个元素与栈顶元素比较大小进行操作，三种情况：大 等 小
// 大：破坏了栈内递增顺序，说明栈顶元素遇到了它右边最大的第一个元素，出栈并记录结果
// 小、等：维持栈内非严格递增顺序，直接入栈
// 精髓在于维持栈的单调顺序，每次填写栈顶元素结果，
// 栈的有序性确保栈顶元素根据当前遍历到的更大的元素找到右边最大的第一个数
// 精简内层循环判断条件，内层循环只处理栈非空且破坏了栈的递增性的元素，每次在内层循环结束后添加元素到栈，表示这个元素遍历过，更具体更清晰的逻辑参考代码随想录对三种逻辑的处理
func dailyTemperatures(temperatures []int) []int {
    res := make ([]int, len(temperatures))
    stack := make([]int, 0)
    for i := 0 ; i<len(temperatures) ; i++{
        // 栈非空且破坏了栈的递增性的元素
        for len(stack)!=0 && temperatures[i]>temperatures[stack[len(stack)-1]] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            res[top] = i - top
        }
        stack = append(stack, i)
    }
    return res
}

496.下一个更大元素 I

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

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

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

示例 1:

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。
对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

示例 2:
输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出-1 。

提示：

1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 10^4
nums1和nums2中所有整数 互不相同
nums1 中的所有整数同样出现在 nums2 中

本题其实和每日温度如出一辙，很明显直接单调栈。但是麻烦的是答案针对的是 nums1 ，而答案的搜索是在 nums2 中的。那咋办？怎么在 nums2 迁移到 nums1 上呢？再看一眼题目，题目说nums1和nums2中所有整数 互不相同 且 nums1 中的所有整数同样出现在 nums2 中，那么nums2和nums1就可以建立起映射关系了。我们最终需要记录的答案数组针对的是 nuns1 ，而答案的记录是通过比较 nuns2 中的元素来实现的，那只要建立 nums1[i] 到 i 的映射关系，就可以便于nums2根据元素确定填写的答案的位置了。

同时答案要求找不到下一个更大元素时填写-1，那答案数组和哈希表同时初始化

1
2
3
4
5
6
7
8
//初始化答案数组
res := make([]int,len(nums1))
//预处理映射关系
hash := make(map[int]int)
for i,num := range nums1 {
    res[i] = -1
    hash[num] = i
}

注意单调栈存放的是下标，比较的时候要记得去原数组中找数哈哈，比较容易记不到

单调栈还是思考三种情况：
遍历元素T[i]大于栈顶元素T[st[len(st)-1]]：弹出栈顶元素，填写栈顶元素答案
遍历元素T[i]等于栈顶元素T[st[len(st)-1]]：入栈（我们需要填写每一个元素的答案，它们都还没遇到右边第一个更大的元素）
遍历元素T[i]小于栈顶元素T[st[len(st)-1]]：入栈

剩下的做法和每日温度几乎一摸一样，唯一的不同在于填写答案要绕一下哈希表再填写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 首先解决nums1和nums2的映射关系，如何确定nums1对应的元素可以快速在nums2中找到
// 单调栈的填写针对一个数组，我们可以很快确定nums2数组中每一个数的答案，但是我们要将结果填写到nums1对应的数组中，所以使用映射关系来存储对应元素的下标
func nextGreaterElement(nums1 []int, nums2 []int) []int {
    //初始化答案数组
    res := make([]int,len(nums1))
    //预处理映射关系
    hash := make(map[int]int)
    for i,num := range nums1 {
        res[i] = -1
        hash[num] = i
    }
    //使用单调栈计算下一个更大的元素，直接存放元素
    stack := make([]int,0)
    for i:=0; i<len(nums2); i++ {
        for len(stack)!=0 && nums2[i]>=stack[len(stack)-1] {
            num := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            if j,ok := hash[num];ok{
                res[j] = nums2[i]
            }
        }
        stack = append(stack, nums2[i])
    }
    return res
}

503.下一个更大元素II

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

示例 1:

输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；数字 2 找不到下一个更大的数；第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
提示:

1 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9

这道题如出一辙，依旧是存索引，只不过是加了个循环数组的要求，那好办。要么将两倍数组拼接在一起，这样就可以实现遍历到尾后还能从头再来；不修改i，遍历两遍原先数组不就完事了，当然涉及到取余来确保访问正确性。

当要求从尾到头再来一遍的时候，一定要想到拼接即可，或者进行多边遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func nextGreaterElements(nums []int) []int {
	//初始化答案数组
	res := make([]int, len(nums))
	for i, _ := range res {
		res[i] = -1
	}
	//单调栈遍历两遍nums，栈存索引
	stack := make([]int, 0)
	for i := 0; i < len(nums)*2; i++ {
		//当前遍历的元素大于栈顶索引的元素
		for len(stack) != 0 && nums[i%len(nums)] > nums[stack[len(stack)-1]] {
			j := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			res[j] = nums[i%len(nums)]
		}
		stack = append(stack, i%len(nums))
	}
	return res
}

接雨水

接雨水有三种做法：

  1. 暴力：按列来计算每一列的雨水，从一列出发寻找左和右的最高列，取min计算本列的雨水
  2. 双指针（官方题解又说是dp）：提前把每一列的左右最高列计算出来，使用的时候直接调用
  3. 更神奇的双指针：左右两个指针对应头和尾，每次根据更小高的数学关系确定哪个指针所在的列的雨水情况
  4. 单调栈，按照行来统计，需要确定凹槽所在位置才能够形成一行的雨水

接雨水就比上述的单调栈要难了，因为需要我们自己去判断单调栈用在什么地方？对于雨水，按照平面来说有两种统计方式：按行和按列。对于按行来统计的方式，需要形成凹槽才能确定接住雨水。那么凹槽应该怎么确定呢？凹槽的结构是中间低，左右高，那么只要底部对应的柱子找到左右两边第一个比它高的柱子，就能够形成凹槽接水。这刚好对应单调栈使用场景，寻找数组中左边/右边第一个更大的元素。那么直接上单调栈就好，栈顶到栈底保持单调递增的顺序。有疑惑，如何找到左边第一个大的元素，很简单，栈内的上一个元素就是左边第一个比它大的元素。

为什么栈内的上一个元素就是左边第一个比它大的元素？栈内存放的元素都是访问过的元素，确保了是左边的元素，并且从栈顶到栈底是单调递增的，上一个元素是大于栈顶元素的。事实上在处理的时候，能够被放入栈且连续，其元素在数组中都是连续递减的，必然是左边第一个最大的。

单调栈存放索引，便于确认宽度和找到高度。

单调栈的三种处理逻辑？
遍历元素T[i]大于栈顶元素T[st[len(st)-1]]：出栈，栈非空则取栈内上一个元素组成凹槽，一低两高，计算一行雨水
遍历元素T[i]等于栈顶元素T[st[len(st)-1]]：替换，因为遇到相同高度的柱子时，计算雨水要拿最右边的柱子去计算，但也可以不出栈，直接加，后续计算的时候会多算一次不正确答案而已
遍历元素T[i]小于栈顶元素T[st[len(st)-1]]：入栈

具体如何计算的？
当遍历元素T[i]大于栈顶元素T[st[len(st)-1]]，出栈得到 mid ，若栈非空则再取栈顶元素 top 组成凹槽，一低两高，一行雨水为 w * h，w = i - top - 1，h = min(height[top], h) - height[mid]

1

柱状图的最大矩形

与接雨水类似，但是在单调栈的使用上，需要寻找左/右两侧更小的第一个元素，据此来决定最大矩形，做法和接雨水可以说是几乎一样

http://willxu0313.github.io/2025/02/15/算法题/单调栈/
作者
Will
发布于
2025年2月15日
许可协议