期末考试终于考完了，泥电的考试实在是折磨人，离散+高数+大物

算起来我好像复习了五天的离散，两天的高数，一个晚上的大物

我真特么厉害…….

现在继续回归写算法吧，github都搁置了好几天了，唉

单调栈#

什么是单调栈，就是单调的栈，要么递增，要么递减，好了没了

然后，单调栈解决的问题是什么：

通常解决“通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。”

为什么要用单调栈：

因为他快，用空间换时间，跟动态规划差不多，不过这个比动态规划更加容易理解反正。

下面需要明白两个性质：

  1. 单调栈中 stack[i]=index 其中 index 是目标数组中的索引
  2. 什么时候单调递增，什么时候单调递减

好 ，下面就用下面这道题来理解一下这个性质。

其中，我们把这个stack 比作 go 中的 slice

然后整个形状可以变成这样

单调递增栈：

这里的slice从左往右数不是单调递增的，为什么还会叫单调递增栈呢？

因为它出栈入栈的比较过程中是单调递增的，到时候就会理解了

大 小 从这里进入

单调递减栈：

同上（为什么叫单调递减栈）

小 大 从这里进入

下面就进入下面这道题来理解一下

每日温度#

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

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

要明白，单调栈是用来记入过程的，记入已经遍历过的数字的过程（这个很抽象）

直接写过程 设置一个单调栈 stack

  1. stack[0] = temp[0] = 3

  2. 如果 temp[i] == stack[栈首]

直接入栈，没什么好说的，因为入栈也是 单调栈，并且它并不是比之前的数字大

  1. 如果 temp[i] < stack[栈首]

因为 temp[i] 是后面的元素，所以 temp[i] 比 之前的元素小并不能说明什么，直接压入栈

  1. 如果 temp[i] > stack[栈首] （栈首的位置是入栈的位置所以要写成）

stack[len(stack)-1]

这种情况下说明 后面来的这个数字比之前的数字大，并且之前的之前的数字都比之前的数字小

举个例子就是： 当 75在栈里面时，则 73,74已经被 75 推出栈了（因为小）

所以后来的数字一定时 第一个比75大的数字

  1. 由此可以明确了三种情况了，最后只要注意一下 栈为空的情况就可以了，最后得出代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func dailyTemperatures(T []int) []int {
	res := make([]int, len(T))
	stack := []int{}

	for i, _ := range T {
		for len(stack) != 0 && T[i] > T[stack[len(stack)-1]] {
			idx := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			res[idx] = i - idx
		}
		stack = append(stack, i)
	}

	return res
}

[!WARNING]

注意不要写成 for T[i] > T[stack[len(stack)-1]] && len(stack) != 0

这样子会报错 out of range ， 具体原因显而易见，反正我是傻逼

[!NOTE]

如果没听懂我的解释，则：代码随想录的解释

下一个更大元素|#

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] 是如上所述的 下一个更大元素 。

建议配合示例理解题目，因为这个题目讲的实在一坨

示例 1：

1
2
3
4
5
6
输入：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与nums2的从头开始遍历，然后选择重合的一个点

那么，下面这个思路绝对牛逼。

首先，如果要找到下一个最大元素，肯定会选择单调栈

其次，要找到nums[i]==nums[j]的情况，我们会找到很多的下一个最大元素选项，那么如果我设立一个Map，如果我得到一个下一个最大元素选项，我就可以用map来判断这个选项是否是Nums1中存在的元素

因此，题目解决了（stack中存的是索引，这个要切记）

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
26
27
28
29
func nextGreaterElement(nums1 []int, nums2 []int) []int {
    res := make([]int, len(nums1))
    for i:= range res {
        res[i] = -1
    }
    mp := map[int]int{}
    for i,v := range nums1 {
        mp[v] = i
    }
    // 单调栈
    stack := []int{}
    stack = append(stack,0)

    for i:=1; i<len(nums2); i++ {
        for len(stack) >0 && nums2[i] > nums2[stack[len(stack)-1]] {

            top := stack[len(stack)-1]

            if _, ok := mp[nums2[top]]; ok {    // 看map里是否存在这个元素
                index := mp[nums2[top]];        // 根据map找到nums2[top] 在 nums1中的下表
                res[index] = nums2[i]
            }

            stack = stack[:len(stack)-1]        // 出栈
        }
        stack = append(stack, i)
    } 
    return res
}