跟着灵茶山艾府大佬学习算法思路的day17（并没有在一个月内掌握hot100）
b站链接如下：
每日温度 题目描述：
给定一个整数数组 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]
示例 2:
1
2
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
示例 3:
1
2
输入: temperatures = [30,60,90]
输出: [1,1,0]
提示：
1 <= temperatures.length <= 10530 <= temperatures[i] <= 100
思路：
这题的暴力是比较好想的，时间复杂度是o(n*2)，优化的思路有两种，可以从左到右，也可以从右到左。
从右到左的思路里，我们可以把数组的数值想象成一座座山，从右到左遍历时，如果遇到一个数比已经遇见过的数要大，对于这些数左边的所有数而言，都只能看到那个更大的数了，不会再往后考虑那个较小的数。
保持从栈底到栈顶的数值递减，如果入栈元素大于栈顶元素，就弹出，直到有栈顶元素大于入栈元素。这个栈顶元素就是待入栈元素后的第一个升高，同时也可以知道入栈元素距离栈顶元素的距离，之后就将待入栈元素入栈。
从左到右也是使用同样单调性的单调栈，但是在更新数组时有所不同。从右到左每次入栈都会更新；而从左到右是在出现一个元素大于站内元素时批量弹出进行更新。从左到右是新元素主动通知栈里的老元素，从右到左是新元素主动问栈里的老元素。
| 从左到右 | 从右到左 | |
|---|---|---|
| 思路 | 当前元素来了，弹走栈里比它小的，它们找到了答案 | 看栈顶能不能当自己的答案 |
| 弹栈时机 | 当前元素比栈顶大时弹 | 当前元素比栈顶小时入栈 |
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var dailyTemperatures = function(temperatures) {
const n = temperatures.length;
const ans = new Array(n).fill(0); // 距离数组
const stack = []; // 存下标，不是温度值
for (let i = n - 1; i >= 0; i--) {
// 栈顶温度小于等于当前温度就弹走，它不可能当答案
while (stack.length && temperatures[stack[stack.length - 1]] <= temperatures[i]) {
stack.pop();
}
// 栈顶就是右边第一个比当前大的位置
if (stack.length) {
ans[i] = stack[stack.length - 1] - i;
// ans[i] = 栈顶下标 - 当前下标
}
stack.push(i);
}
return ans;
};
总结：
时间复杂度是o(n)，空间复杂度是o(min(n, U))，U为数组最大值减去最小值。