739. 每日温度

[S-T-D]

• 原题地址
• 题目描述
• 题解 —— 暴力
  • 思路
  • 代码
  • 复杂度
• 题解 —— 单调栈
  • 思路
  • 代码
  • 复杂度
     

原题地址

https://leetcode-cn.com/problems/daily-temperatures/)

 

题目描述

请根据每日 气温 列表 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]

示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]
 

提示：
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100

 

题解 —— 暴力

思路

从后往前遍历

代码

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function(temperatures) {
    const len = temperatures.length;
    const res = new Array(len).fill(0);

    for (let i = len - 2; i >= 0; i--) {
        if (temperatures[i] < temperatures[i + 1]) {
            res[i] = 1;
        } else {
            let j = i + 1;
            while (res[j] !== 0 && (j = j + res[j]) < len) {
                if (temperatures[i] < temperatures[j]) {
                    res[i] = j - i;
                    break;
                } else {
                    continue;
                }
            }
        }
    }
    
    return res;
};

复杂度

• 时间：O(n^2)
• 空间：O(n)

 

题解 —— 单调栈

思路

代码

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function(temperatures) {
    const len = temperatures.length;
    const res = new Array(len).fill(0);
    const stack = [];

    for (let i = 0; i < len; i++) {
        const t = temperatures[i];
        while (stack.length && t > temperatures[stack[stack.length - 1]]) {
            const prevIndex = stack.pop();
            res[prevIndex] = i - prevIndex;
        }
        stack.push(i);
    }
    
    return res;
};

复杂度

• 时间：O(n)
• 空间：O(n)