代码随想录训练营 DP

最近有点不上心

42. 接雨水🌸

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

func trap(height []int) int {
	var left, right, leftMax, rightMax, res int
	right = len(height) - 1
	for left < right {
		if height[left] < height[right] {
			if height[left] >= leftMax {
				leftMax = height[left]  // 设置左边最高柱子
			} else {
				res += leftMax - height[left]  // //右边必定有柱子挡水，所以遇到所有值小于等于leftMax的，全部加入水池中
			}
			left++
		} else {
			if height[right] > rightMax {
				rightMax = height[right]  // //设置右边最高柱子
			} else {
				res += rightMax - height[right]  // //左边必定有柱子挡水，所以，遇到所有值小于等于rightMax的，全部加入水池
			}
			right--
		}
	}
	return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

503.下一个更大元素II🌸

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

func nextGreaterElements(nums []int) []int {
    length := len(nums)
    result := make([]int,length,length)
    for i:=0;i<len(result);i++{
        result[i] = -1
    }
    //单调递减，存储数组下标索引
    stack := make([]int,0)
    for i:=0;i<length*2;i++{
        for len(stack)>0&&nums[i%length]>nums[stack[len(stack)-1]]{
            index := stack[len(stack)-1]
            stack = stack[:len(stack)-1] // pop
            result[index] = nums[i%length]
        }
        stack = append(stack,i%length)
    }
    return result
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18