今日内容：

1. LeetCode503 下一个更大元素Ⅱ
2. LeetCode42 接雨水

资料来源：

1. 代码随想录 | LeetCode503 下一个更大元素Ⅱ
2. 代码随想录 | LeetCode42 接雨水

1 LeetCode503 下一个更大元素Ⅱ

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

输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]

这题和每日温度差不多，它和每日温度的唯一的区别在于，它的数组是可循环的。可以对给定的数组循环两次，别的都一样。

go
func nextGreaterElements(nums []int) []int {
	if len(nums) == 1 {
		return []int{-1}
	}
	
	result := make([]int, len(nums))
	for i := range result {
		result[i] = -1
	}
	stack := []int{0}
	for i := 1; i <= len(nums) * 2 - 1; i++ {
		front := stack[len(stack) - 1]
		if nums[front] >= nums[i % len(nums)] {
			stack = append(stack, i % len(nums))
		} else { // 一直移除栈顶元素
			for len(stack) != 0 && nums[i % len(nums)] > nums[front] {
				result[front] = nums[i % len(nums)]
				stack = stack[:len(stack) - 1]
				if len(stack) != 0 {
					front = stack[len(stack) - 1]
				}
			}
			stack = append(stack, i % len(nums))
		}
	}
	
	return result
}

2 LeetCode42 接雨水

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

输入：height = [4,2,0,3,2,5]
输出：9

这题需要先想明白，如何统计雨水？对于每一横行来说，每次统计有多少雨水就需要知道的是它的长度，高度。又对于每个竖列来说，每一行的长度就是它左边的比它高的第一个列到它右边比它高的第一个列的距离，每一行的高度就是这两个比自己高的列中较低的那个和自己的高度差值。那么按照竖列找到左右比它高的竖列，就是单调栈应该做的了。每次比较中，如果栈顶的元素小于准备进入栈的元素，栈顶的第一个元素就是要计算的竖列，栈顶的第二个元素就是栈顶元素那个竖列的左侧的比它高的元素，准备进入栈的元素就是栈顶元素那个竖列的右侧比它高的元素。

在以上的分析中，已经明确了单调栈比较大小的大或者小两种情况。那么如果想要进入栈的元素和栈顶元素相同呢？这时必须弹出栈顶元素，再加入新的元素，以防止[5, 5, 1, 7]这种情况。如果不先弹出元素再加入新的元素，在1处准备计算雨水时，长度就会从第一个元素开始计算，导致结果错误。

go
func trap(height []int) int {
	if len(height) == 1 || len(height) == 2 {
		return 0
	}
	
	result := 0
	stack := []int{0}
	for i := 1; i < len(height); i++ {
		top := stack[len(stack) - 1]
		if height[i] == height[top] {
			stack = stack[:len(stack) - 1]
			stack = append(stack, i)
		} else if height[i] < height[top] {
			stack = append(stack, i)
		} else {
			for len(stack) != 0 && height[i] > height[top] {
				middle := top
				stack = stack[:len(stack) - 1] // 弹出
				if len(stack) != 0 {
					top = stack[len(stack) - 1]
					h := min(height[top], height[i]) - height[middle]
					l := i - top - 1
					result += h * l
				}
			}
			stack = append(stack, i)
		}
	}
	
	return result
}