今日内容：

1. LeetCode739 每日温度
2. LeetCode496 下一个更大元素 Ⅰ

资料来源：

1. 代码随想录 | LeetCode739 每日温度
2. 代码随想录 | LeetCode496 下一个更大元素 Ⅰ

1 LeetCode739 每日温度

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

输入: temperatures = [30,60,90]
输出: [1,1,0]

单调栈，顾名思义，和单调队列一样，是一种在栈的基础上维护内部数据的单调性的数据结构。它所代表的题目一般具有“求左/右边的第一个更大元素”的特征。

Go语言没有自己实现的栈，一般如果需要用栈的话有三种方案：自己实现栈，用切片模拟栈和用container/list双向链表来模拟栈。之后的所有单调栈题目都会用第二种方法。

以维护一个从栈顶到栈底单调递增的单调栈为例，每次元素试图入栈时，都需要和栈顶元素进行比较。如果元素和栈顶元素相同，需要根据题目要求确实是否进入栈；如果元素大于栈顶元素，则出栈一次后继续比较，直到栈空或者栈顶元素比入栈元素要大；如果元素小于栈顶元素，则直接入栈。

就本题来说，它要找的是当前元素右侧比它大的第一个元素和它的距离，那么单调栈内可以存元素的下标，从而再出栈时同时获取元素的下标和比该元素大的元素的下标。另外，本题如果元素相等也要入栈，因为元素相等也要找那个更大的元素。

go
func dailyTemperatures(temperatures []int) []int {
	result := make([]int, len(temperatures))
	stack := []int{0}
	for i := 1; i < len(temperatures); i++ {
		top := stack[len(stack) - 1]
		if temperatures[i] > temperatures[top] { // 如果栈顶元素小于新元素 就移除栈顶元素 将新元素加入
			for len(stack) != 0 && temperatures[i] > temperatures[top] { // len(stack) != 0 经常忘
				result[top] = i - top
				stack = stack[:len(stack) - 1] // 移除最后的元素
				if len(stack) != 0 {
					top = stack[len(stack) - 1]
				}
			}
			stack = append(stack, i)
		} else if temperatures[i] <= temperatures[top] { // 栈顶元素大于等于新元素 直接加入
			stack = append(stack, i)
		}
	}
	return result
}

2 LeetCode496 下一个更大元素 Ⅰ

输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3, 4 ,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [ 1 ,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4, 2 ]。不存在下一个更大元素，所以答案是 -1 。

输入：nums1 = [2,4], nums2 = [1,2,3,4].
输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 2 ，用加粗斜体标识，nums2 = [1, 2 ,3,4]。下一个更大元素是 3 。
- 4 ，用加粗斜体标识，nums2 = [1,2,3, 4 ]。不存在下一个更大元素，所以答案是 -1 。

这题和上一个题很像，但是在单调栈的处理之上又多了一层去nums1寻找元素位置的逻辑，其他的和上一题区别不大。

go
func nextGreaterElement(nums1 []int, nums2 []int) []int {
	result := make([]int, len(nums1))
	resultMap := map[int]int{} // 存储nums1中的元素和下标对应关系
	for i := range nums1 {
		result[i] = -1 // 初始化 找不到就是-1
		resultMap[nums1[i]] = i
	}
	
	stack := []int{0}
	for i := 1; i < len(nums2); i++ {
		top := stack[len(stack) - 1]
		if nums2[i] > nums2[top] {
			for len(stack) != 0 && nums2[i] > nums2[top] {
				if val, ok := resultMap[nums2[top]]; ok {
					result[val] = nums2[i]
				}
				stack = append(stack[:len(stack) - 1])
				if len(stack) != 0 {
					top = stack[len(stack) - 1]
				}
			}
			stack = append(stack, i)
		} else {
			stack = append(stack, i)
		}
	}
	
	return result
}