代码随想录：单调栈

2024-05-29 2025-04-08 约 2300 字预计阅读 5 分钟 - 次阅读 - 条评论

每日温度

1
2
3
4
5
6
7
8


func main() {
    temperatures := []int{73, 74, 75, 71, 69, 72, 76, 73}
    r := dailyTemperatures(temperatures)
    fmt.Println(r) // [1,1,4,2,1,1,0,0]
}
func dailyTemperatures(temperatures []int) []int {
    // ......
}

分析

参考了官解：方法二：单调栈

维护一个温度单调递减的栈（使用队列模拟），栈中不直接存温度，而是温度的下标i（这样方便计算两个温度之间的天数间隔）

遍历数组：

如果当前temper[i]值小于栈顶元素，则直接将i加入到栈中；
如果当前temper[i]值大于栈顶元素，则将其前面小于temper[i]的元素全部弹出栈；

在元素弹出栈时，需要更新每个弹出元素outIndex的res数组值（也就是说，如果某个元素弹出栈了，说明找到了比它温度高的i，则更新res[outIndex]=i-outIndex）。
如果栈为空，则直接将i加入到栈中。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


func dailyTemperatures(temperatures []int) []int {
    n := len(temperatures)
    res := make([]int, n)
    minStack := make([]int, 0)
    for i, temper := range temperatures {
       for len(minStack) > 0 && temper > temperatures[minStack[len(minStack)-1]] { // 新加入元素比栈顶元素大
          outIndex := minStack[len(minStack)-1] // 需要出栈的下标
          minStack = minStack[:len(minStack)-1] // 将栈顶元素出栈
          res[outIndex] = i - outIndex          // i位置就是outIndex位置的后一个更高温度的下标
       }
       minStack = append(minStack, i) // 栈大小为空 或者 添加的元素小于栈顶元素，直接加入到栈中
    }
    return res
}

下一个更大元素I

496. 下一个更大元素 I

1
2
3
4
5
6
7
8


func main() {
    nums1, nums2 := []int{4, 1, 2}, []int{1, 3, 4, 2}
    r := nextGreaterElement(nums1, nums2)
    fmt.Println(r) // [-1,3,-1]
}
func nextGreaterElement(nums1 []int, nums2 []int) []int {
    // ......
}

分析

求nums2数组中下一个大于nums1[i]的元素。

由于我们需要到到nums2数组中去找nums1的元素，所以我们需要将nums1的元素存入map中（key为元素值，value为元素下标）。

然后遍历nums2数组，维护一个单调递减（从栈底到栈顶）的单调栈，遍历元素时，需要判断该元素是否在nums1中存在。

后面维护单调栈的过程就和每日温度相同了，栈中存的下标值，而不是元素值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


func nextGreaterElement(nums1 []int, nums2 []int) []int {
    res := make([]int, len(nums1))
    for i := 0; i < len(nums1); i++ { // res数组初始化为-1
       res[i] = -1
    }
    nums1Map := make(map[int]int, len(nums1)) // key为元素值，value为元素下标
    for i, num := range nums1 {
       nums1Map[num] = i
    }
    minStack := make([]int, 0) // 栈中存的是下标
    for i, num := range nums2 {
       for len(minStack) > 0 && num > nums2[minStack[len(minStack)-1]] {
          stackPop := minStack[len(minStack)-1] // 栈顶元素，注意是nums2的下标
          minStack = minStack[:len(minStack)-1]
          if nums1Index, exist := nums1Map[nums2[stackPop]]; exist { // 如果出栈的元素在nums1中存在
             res[nums1Index] = num // 找到stackPop在nums1中的下标位置，并更新下一个更大的数为num
          }
       }
       minStack = append(minStack, i) // 将下标存入栈中
    }
    return res
}

下一个更大元素II

503. 下一个更大元素 II

1
2
3
4
5
6
7
8
9


func main() {
    nums := []int{1, 2, 1}
    //nums := []int{1, 2, 3, 4, 3} // [2,3,4,-1,4]
    r := nextGreaterElements(nums)
    fmt.Println(r) // [2,-1,2]
}
func nextGreaterElements(nums []int) []int {
    // ......
}

分析

自己的想法： 将nums数组拼接上一个nums数组。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


func nextGreaterElements(nums []int) []int {

	n := len(nums)
	nums = append(nums, nums...)
	fmt.Println(nums)
	res := make([]int, n)
	for i := range res {
		res[i] = -1
	}
	minStack := make([]int, 0)
	for i, num := range nums {
		for len(minStack) > 0 && num > nums[minStack[len(minStack)-1]] {
			stackTop := minStack[len(minStack)-1]
			if stackTop >= n {
				stackTop %= n
			}
			res[stackTop] = num
			fmt.Println(res)
			minStack = minStack[:len(minStack)-1]
		}
		minStack = append(minStack, i)
	}
	return res
}

方法2： 使用%（下标取余）的方式来模拟数组成环的过程。不用真正地去将原数组扩充，而是让下标去循环遍历。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func nextGreaterElements(nums []int) []int {
    n, realI := len(nums), 0
    res := make([]int, n)
    for i := range res {
       res[i] = -1
    }
    minStack := make([]int, 0)
    for i := 0; i < 2*n; i++ { // 这里i从0到2n-1
       realI = i % n // 循环遍历，真正的下标
       for len(minStack) > 0 && nums[realI] > nums[minStack[len(minStack)-1]] {
          stackTop := minStack[len(minStack)-1]
          res[stackTop] = nums[realI]
          minStack = minStack[:len(minStack)-1]
       }
       minStack = append(minStack, realI)
    }
    return res
}

接雨水

42. 接雨水

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


func main() {
    height := []int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}
    r := trap(height)
    fmt.Println(r) // 6
    // 010210132121
    //        o
    //    o×××oo×o
    //  o×oo×oooooo
    // ×位置就是可以接雨水的位置，总共可以接6个单位的雨水。
}
func trap(height []int) int {
    // ......
}

分析

代码随想录的思路：使用单调栈。

我们需要确定i位置左边第1个大于它的位置和右边第1个大于它的。

我们可以使用最小栈（栈顶元素最小）来完成。

如果遇到的元素小于栈顶元素，直接将其添加到栈中。（添加的是下标）

如果遇到的元素大于栈顶元素，则i位置的右侧边界就找到了，也就是收获结果的时候。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


func trap(height []int) int {
    sumArea := 0
    minStack := make([]int, 0)
    for i, h := range height {
       for len(minStack) > 0 && h > height[minStack[len(minStack)-1]] {
          stackTop := minStack[len(minStack)-1]
          minStack = minStack[:len(minStack)-1] // 删除栈顶元素
          if len(minStack) > 0 {
             lIndex := minStack[len(minStack)-1]  // 左侧位置就是删除一个元素之后的栈顶值
             sumArea += (min(height[lIndex], h) - height[stackTop]) * (i - lIndex - 1) // 计算当前位置的面积，并加入到sum中
          }
       }
       minStack = append(minStack, i)
    }
    return sumArea
}

双指针的思路可以参考：LeetCode 热题 100-接雨水。

柱状图中最大的矩形

84. 柱状图中最大的矩形

1
2
3
4
5
6
7
8


func main() {
    heights := []int{2, 1, 5, 6, 2, 3}
    r := largestRectangleArea(heights)
    fmt.Println(r) // 10
}
func largestRectangleArea(heights []int) int {
    // ......
}

分析

使用单调栈来实现。

在i位置，我们需要找到左边第1个比它小的位置leftIndex和右边第1个比它小的位置rightIndex，i位置的最大宽度就是rightIndex-leftIndex-1。

我们需要维护一个最大栈，也就是栈顶元素最大，栈顶到栈底依次递减（可以相等）。具体如下：

如果遇到的元素比栈顶元素大（或者等），则直接将其添加到栈中（添加的是元素的下标）；
如果遇到的元素比栈顶元素小（右边就不能继续往后延展了），就是我们需要收获结果的时候。

我们计算以栈顶元素stackTop的值为高度，能形成的最大矩形

矩形的左侧位置就是栈顶元素stackTop在栈中的前一个位置（比栈顶位置值大）
矩形的右侧位置就是我们遇到的元素位置

这样计算一个面积值之后，更新maxArea的值。

然后将栈中比添加元素大的元素全部弹出，将遇到的元素加入到栈中。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


func largestRectangleArea(heights []int) int {
	newHeights := make([]int, len(heights)+2) // 为了能够正常收获结果，在原数组的首尾加上0
    newHeights[0], newHeights[len(newHeights)-1] = 0, 0
    for i := 1; i < len(newHeights)-1; i++ {
       newHeights[i] = heights[i-1]
    }
    maxStack := make([]int, 0)
    curArea, maxArea := 0, 0
    for i, h := range newHeights {
       for len(maxStack) > 0 && h < newHeights[maxStack[len(maxStack)-1]] { // h比栈顶元素小
          stackTop := maxStack[len(maxStack)-1]
          maxStack = maxStack[:len(maxStack)-1] // 将栈顶元素弹出
          lIndex := maxStack[len(maxStack)-1]   // 左侧的位置就是弹出一个元素之后的栈顶值
          curArea = (i - lIndex - 1) * newHeights[stackTop]
          maxArea = max(maxArea, curArea)
       }
       maxStack = append(maxStack, i)
    }
    return maxArea
}

收录于合集・代码随想录 7

代码随想录：额外题目