每日温度
🟡 中等题目描述
给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，则用 0 来代替。
示例 1
输入：temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
输出：[1, 1, 4, 2, 1, 1, 0, 0]示例 2
输入：temperatures = [30, 40, 50, 60]
输出：[1, 1, 1, 0]提示
1 <= temperatures.length <= 10^530 <= temperatures[i] <= 100
解法
参考答案 (2 个标签)
单调栈 O(n)
思路
使用单调递减栈存储下标。当遇到更高温度时，弹出栈中所有比当前温度低的元素，计算天数差。
代码实现
/**
* @param {number[]} temperatures
* @return {number[]}
*/
function dailyTemperatures(temperatures) {
const n = temperatures.length;
const answer = new Array(n).fill(0);
const stack = [];
for (let i = 0; i < n; i++) {
while (
stack.length > 0 &&
temperatures[i] > temperatures[stack[stack.length - 1]]
) {
const prevIndex = stack.pop();
answer[prevIndex] = i - prevIndex;
}
stack.push(i);
}
return answer;
}复杂度分析
- 时间复杂度：O(n)，每个元素最多入栈出栈一次
- 空间复杂度：O(n)
图解
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
i=0: stack=[0]
i=1: 74>73, 弹出0, answer[0]=1, stack=[1]
i=2: 75>74, 弹出1, answer[1]=1, stack=[2]
i=3: 71<75, stack=[2,3]
i=4: 69<71, stack=[2,3,4]
i=5: 72>69, 弹出4, answer[4]=1
72>71, 弹出3, answer[3]=2
72<75, stack=[2,5]
i=6: 76>72, 弹出5, answer[5]=1
76>75, 弹出2, answer[2]=4
stack=[6]
i=7: 73<76, stack=[6,7]
answer = [1, 1, 4, 2, 1, 1, 0, 0]