739\. 每日温度
# 739. 每日温度 (opens new window)
# Description
Difficulty: 中等
Related Topics: 栈 (opens new window), 数组 (opens new window), 单调栈 (opens new window)
给定一个整数数组 temperatures
,表示每天的温度,返回一个数组 answer
,其中 answer[i]
是指对于第 i
天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0
来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
1
2
2
示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
1
2
2
示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]
1
2
2
提示:
- 1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100
# Solution
Language: JavaScript
/**
* @param {number[]} temperatures
* @return {number[]}
*/
var dailyTemperatures = function(temperatures) {
let n = temperatures.length;
let res = new Array(n).fill(0)
// 单调栈
let stack = [0]
// 遍历每日温度,维护一个单调栈
for (let i = 1; i < n; i++) {
while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
const top = stack.pop()
res[top] = i - top
}
// 栈为空 或 每日温度小于等于栈顶温度 => 直接入栈
stack.push(i)
}
return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23