LeetCode739. 每日温度(栈问题进阶)｜刷题打卡

川长思鸟来 2022-11-05 12:53 64阅读 0赞

# 一、题目描述 #

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = \[73, 74, 75, 71, 69, 72, 76, 73\]，你的输出应该是 \[1, 1, 4, 2, 1, 1, 0, 0\]。

**提示**：气温 列表长度的范围是 \[1, 30000\]。每个气温的值的均为华氏度，都是在 \[30, 100\] 范围内的整数。

# 二、思路分析 #

## 暴力解法 ##

看到这个题目后，我首先想到的就是直接暴力解法：

但是写出来代码之后一看，一个数组两层遍历，这暴力解法，时间复杂度直接飙到了**O(n^2)**，这在面试中显然是难以令面试官满意的。

所以得想办法优化优化。

## 利用栈避免重复操作 ##

其实我们在暴力循环的过程中做了很多重复功。

[73, 74, 75, 71, 69, 72, 76, 73]

拿 75 来说，我们在找比 75 高的第一个温度的过程中，就路过了 71、69、72 、76，其中，72 正是 71 对应的目标温度。

当外层循环走到 71 时，我们才又重复了一遍刚刚走过的路：69 、72。

![a8e91489175ab2a69e76ca2c26aa606e.png][]

我们得想办法减少这种重复：**利用栈结构可避免重复操作。**

尝试去维持一个**递减栈**：

*  遍历温度，单调递减时将索引入栈；
 *  当一个温度将打破这个单调递减趋势(比前一个温度值高)时，将栈顶索引出栈，这两个温度的索引差，就是前一个温度需要等待的天数。

在这个过程中，整个数组只会被遍历一次，期间只进行了一些入栈、出栈操作，因此时间复杂度就是**O(n)**。

# 三、AC 代码 #

/**
     * @param {number[]} T
     * @return {number[]}
     */
    // 入参是温度数组
    const dailyTemperatures = function(T) {
        const len = T.length // 缓存数组的长度 
        const stack = [] // 初始化栈
        const res = (new Array(len)).fill(0) //初始化结果数组默认值为0
        for(let i=0;i<len;i++) {
          // 若栈不为空，且温度值将要打破递减趋势
          while(stack.length && T[i] > T[stack[stack.length-1]]) {
            // 将栈顶温度值对应的索引出栈
            const top = stack.pop()  
            // 当前栈顶温度值与将要打破递减趋势的温度值(第一个高于它的温度值)的索引差值即为等待天数
            res[top] = i - top 
          }
          // 入栈温度值索引，方便计算天数
          stack.push(i)
        }
        // 返回结果数组
        return res 
    };

# 四、总结 #

*  暴力遍历一定得优化；
 *  栈结构可以帮我们避免重复操作；
 *  及时地将不必要的数据出栈。

[a8e91489175ab2a69e76ca2c26aa606e.png]: /images/20221023/3529eb5703034c16bf387f03bba173b1.png