单调栈

# 单调栈

场景：寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置 单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是整个数组只需要遍历一次。在使用单调栈的时候首先要明确如下几点：

单调栈里存放的元素是什么？

单调栈里只需要存放元素的下标i就可以了，如果需要使用对应的元素，直接T[i]就可以获取。

单调栈里元素是递增呢？还是递减呢？

如果求一个元素右边第一个更大元素，单调栈就是递增的，

如果求一个元素右边第一个更小元素，单调栈就是递减的。

使用单调栈主要有三个判断条件：

当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况

当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况

当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

# 每日温度 (opens new window)

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]

func dailyTemperatures(temperatures []int) []int {
    st := []int{}
    ans := make([]int, len(temperatures))
    for i:=len(temperatures)-1; i>=0; i-- {
        for len(st) > 0 && temperatures[i] >= temperatures[st[len(st)-1]] {
            st = st[:len(st)-1]
        }
        if len(st) > 0 {
            ans[i] = st[len(st)-1] - i
        }
        st = append(st, i)
    }
    return ans
}

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

# 下一个更大元素 I (opens new window)

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置右侧的 第一个 比 x** 大的元素。给你两个 没有重复元素** 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。返回一个长度为 nums1.length 的数组_ ans 作为答案，满足 ans[i] _是如上所述的 下一个更大元素 。

// 2024.07.21
func nextGreaterElement(nums1 []int, nums2 []int) []int {
    m := map[int]int{}
    for i:=0; i<len(nums1); i++ {
        m[nums1[i]] = i
    }

    st := []int{}
    for i:=len(nums2)-1; i>=0; i-- {
        for len(st) > 0 && nums2[i] >= st[len(st)-1] {
            st = st[:len(st)-1]
        }

        if index, ok := m[nums2[i]]; ok {
            if len(st) > 0 {
                nums1[index] = st[len(st)-1]
            } else {
                nums1[index] = -1
            }
        } 
        st = append(st, nums2[i])
    }

    return nums1
}

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

# 下一个更大元素 (opens new window)2-循环数组

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

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

	st := make([]int, 0)
	for i := len(nums) - 1; i >= 0; i-- {
		for len(st) > 0 && nums[i] >= st[len(st)-1] {
			st = st[:len(st)-1]
		}
		st = append(st, nums[i])
	}

	for i := len(nums) - 1; i >= 0; i-- {
		for len(st) > 0 && nums[i] >= st[len(st)-1] {
			st = st[:len(st)-1]
		}
        tmp := nums[i]  	//易错点，如果原地修改数组，这里需要将原数据保存起来，后面再
		if len(st) == 0 {
			nums[i] = -1
		} else {
			nums[i] = st[len(st)-1]
		}
		st = append(st, tmp)
	}
	return 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

# 接雨水 (opens new window)

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

（1）方法一：左右扫描

核心思想：将每个纵方向的左右最高墙统计出来，当左右均有更高墙的时，即可接雨水

func trap(height []int) int {
    n := len(height)
    if n==0 {
        return 0
    }
    leftMax := make([]int, n)   //统计在左边的柱子
    leftMax[0] = height[0]
    for i:=1; i < n; i++ {
        leftMax[i] = max(leftMax[i-1], height[i])
    }

    rightMax := make([]int, n)	//统计在右边的柱子
    rightMax[n-1] = height[n-1]
    for i:=n-2; i>=0 ; i-- {
        rightMax[i] = max(rightMax[i+1], height[i])
    }

    ans := 0
    for i:=0; i<n;i++ {
        ans += min(leftMax[i], rightMax[i])  - height[i] //左右墙的min-自己高度 == 接水容量
    }
    return ans
}

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

（2）方法二：单调栈

核心思想：当形成凹槽时即可装下雨水，统计形成的每一个凹槽容量。

func trap(height []int) int {
    st, res := []int{}, 0
    
    for i:=0; i<len(height); i++ {
        for len(st) > 0 && height[st[len(st)-1]] < height[i] {
            mid := height[st[len(st)-1]]  	//凹槽底部高度
            st = st[:len(st)-1]
            if len(st) > 0 {                //左边有墙
                h := min(height[i], height[st[len(st)-1]]) - mid 
                w := i - st[len(st)-1] - 1	//凹槽宽度
                res += h*w
            }
        }
        st = append(st, i)
    }
    return res
}

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

# 接雨水 II (opens new window)（二维）

给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。

# 柱状图中最大的矩形 (opens new window)

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。单调栈：非单调递增时，则发现右边界。左边界只需要st栈的上一个数，即距离最小的比nums[i]小左边界

func largestRectangleArea(heights []int) int {
    res := 0
    st := []int{0}
    heights = append([]int{0}, heights...)
    heights = append(heights, 0)
    for i:=1; i<len(heights); i++ {
        for len(st) > 0 && heights[st[len(st)-1]] > heights[i] {
            mid := st[len(st)-1] 
            st = st[:len(st)-1]
            left := st[len(st)-1]  //易错点，这里找到上一个比自己矮的, 作为矩形的左边界
            res = max(res, heights[mid] * (i-left-1))
        }
        st = append(st, i)
    }
    return res
}

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

编辑

上次更新: 2024/09/13, 11:59:12

← 回溯链表和树→