天气题库

每日温度

请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 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]

思路:

:::details 点击查看代码

function dailyTemperatures(temperatures) {
    let length=temperatures.length;
    let result=new Array(length).fill(0);
    let stack=[];
    for(let i=0;i<length;i++){
        let temperature=temperatures[i];
        while(stack.length&&temperature>temperatures[stack[stack.length-1]]){
            let prevIndex=stack.pop();
            result[prevIndex]=i-prevIndex;
        }
        stack.push(i);
    }
    return result;
};

:::

性能分析:

• 时间复杂度：O(n)，其中 n 是温度列表的长度。正向遍历温度列表一遍，对于温度列表中的每个下标，最多有一次进栈和出栈的操作。
• 空间复杂度：O(n)，其中 n 是温度列表的长度。需要维护一个单调栈存储温度列表中的下标。