每日温度 - Stellar Observer Protocol

564 字

3 分钟

每日温度

2025-08-22

Algorithms

数组

/

栈

/

单调栈

题目描述#

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

解题思路#

单调栈策略：
- 使用栈存储尚未找到更高温度的日期索引
- 维护栈内温度值单调递减的特性
温度比较机制：
- 遍历每日温度，与栈顶温度比较
- 若当前温度更高，则计算日期差并更新答案
索引存储优化：
- 栈中存储日期索引而非温度值
- 通过索引访问温度和设置结果
结果初始化：
- 默认所有结果值为0（无更高温度）
- 仅更新找到更高温度的日期

关键洞察#

单调性利用：
- 栈内温度保持递减顺序
- 确保栈顶总是最近待解决的日期
跳跃性更新：
- 弹出栈顶元素时可连续更新多个日期
- 避免重复遍历相同区间
时空平衡：
- 牺牲O(n)空间获得O(n)时间复杂度
- 显著优于暴力解法的O(n²)
边界处理：
- 栈空时无需操作
- 遍历结束栈中剩余日期保持0

复杂度分析#

指标	说明
时间复杂度	O(n)：每个日期最多入栈出栈一次
空间复杂度	O(n)：栈的空间开销（最坏情况存储n个索引）

代码实现#

1
/**
2
 * @param {number[]} temperatures
3
 * @return {number[]}
4
 */
5
var dailyTemperatures = function (temperatures) {
6
    const n = temperatures.length;
7
    const result = new Array(n).fill(0);
8
    const stack = [
9
        {
10
            index: 0,
11
            t: temperatures[0]
12
        }
13
    ]
14

15
    for (let i = 1; i < n; i++) {
16
        const t = temperatures[i];
17
        while (stack.length!==0 && stack[stack.length - 1].t < t) {
18
            const { index } = stack.pop();
19
            result[index] = i - index;
20
        }
21
        stack.push({ index: i, t })
22
    }
23

24
    return result;
25
};