每日温度

[Cosen95]

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

[Cosen95]

题目难度medium，涉及到的算法知识有栈。

题目描述

根据每日气温列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用  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)，显然不是最优解法。

本道题目可以采用栈去做一个优化。

大概思路就是：维护一个递减栈。当遍历过的温度，维持的是一个单调递减的态势时，我们就对这些温度的索引下标执行入栈操作；只要出现了一个数字，它打破了这种单调递减的趋势，也就是说它比前一个温度值高，这时我们就对前后两个温度的索引下标求差，得出前一个温度距离第一次升温的目标差值。

代码实现

/**
 * @param {number[]} T
 * @return {number[]}
 */
var dailyTemperatures = function(T) {
    const len = T.length;
    const stack = [];
    const res = (new Array(len)).fill(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
};