单调栈---每日温度

题目描述

leetcode地址

源码地址

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

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

这个输出我看了半分钟才看明白，可能需要解释一下：

屏幕快照 2021-06-02 下午3.13.33.png

从第0天开始，第1天的温度比它高，意思就是第0天需要等待1天就能观测到更高的气温，所以下标0填1。

第2天温度比第1天高，则第1天同样仅需等待1天就能观测到更高到气温，所以下标1也填1。

第2天的温度是75，往后第3，4，5天的温度都低于第2天，到了第6天温度才高于第2天，所以第2天需要等待4天才能观测到更高气温，下标2填4。

第6天的温度是76，往后的每一天的温度都比它低，也就是等不到能观测到比第6天更高气温的那天，按题目要求填0.

第7天是最后一天，没有参照物比较，也填0.

最后正确的输出就应该是：[1, 1, 4, 2, 1, 1, 0, 0]

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

方法一：暴力解法

思路：
这个题目简单理解就是对于位置i，找到位置j，位置j是满足：

• j > i
• temperatures[j] > temperatures[i]

两个条件的最小下标。

所以对于每个位置，都从该位置+1的地方往后遍历，找到第一个大于它的值，计算两个下标差值即可。

代码：

var dailyTemperatures = function(temperatures) {
    let len = temperatures.length
    if(len <= 0) return []
    let res = []
    // 最后一个元素后面一定没有比它大的值
    res[len-1] = 0
    for(let i = len-2; i >= 0; i--) {
        let target = temperatures[i]
        for(let j = i+1; j < len; j++) {
            let current = temperatures[j]
            if(current > target) {
                res[i] = j-i
                break;
            }
        }
        // 这里的意思是该位置后面没有出现过比它大的值
        if(res[i] === undefined) {
            res[i] = 0;
        }
    }
    return res;
};

性能：
时间复杂度：O(n^2)
空间复杂度：O(n)

屏幕快照 2021-06-02 下午5.58.20.png

方法二：单调栈

单调栈就是栈中的元素满足单调递增或递减。

思路：
如果相邻位置的两个数，前一个数小于后一个数，则很明显，前一个位置的结果就是1，即只需要等待一天。
如果前一个数大于后一个数，则前一个位置的结果不能确定，需要指针继续向后走，直到一个比它大的数出现，才能知道其需要等待的天数。

也就是说，对于每个位置来说，都只需要找到往后最小的下标，满足其气温高于当前位置。

对于暂时还未找到更高气温的位置，存入栈中，指针每一次向后移动时，和栈中元素比较，如果发现更高，表示栈中存放的元素可以确定等待天数了，则该元素出栈。

按这个思路你会发现，能存入栈中的元素，满足一个条件：栈中元素是递减的（从栈底到栈顶），不会存在新入栈的元素比栈顶元素更大的情况，因为这种情况下，栈顶元素就直接出栈了（已经找到了等待天数自然就不会呆在栈中了）

当栈顶元素出栈后，栈顶变成了之前的第二位元素，此时，新栈顶元素和指针指向的元素大小关系如何呢？比较一下就知道了，如果新栈顶元素也能出栈，则继续比较，直到栈空。如果不能出栈，将指针指向元素推入栈中，指针继续向后移动。

好了，这就是解题思路了。

来个例子理解一下。

温度列表：temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
指针：p = 0
单调栈：stack = []
结果: res = []

p=0时，栈空，0直接入栈, stack=[0]
p=1时，栈顶值是0，temperatures[1]大于temperatures[0]，0出栈，同时res[0] = 1-0, 此时栈空，1直接入栈, stack=[1]
p=2同理，res[1] = 2-1, stack=[2]
p=3时, 栈顶值是2，temperatures[3]小于temperatures[2]，3入栈, stack=[2, 3]
p=4时，栈顶值是3，temperatures[4]小于temperatures[3]，4入栈，stack=[2, 3, 4]
p=5时，此时栈中元素如下：

image.png
栈顶值是4，temperatures[5]大于temperatures[4]，4可以出栈，同时res[4] = 5-4,
此时栈中还有元素，栈顶值变成3，继续比较。
temperatures[5]大于temperatures[3]，3可以出栈，同时res[3] = 5-3，此时栈中还有元素，栈顶值变成2，继续比较。
temperatures[5]小于temperatures[2]，5入栈，stack=[2, 5]

p=6时，栈顶值是5，temperatures[6]大于temperatures[5]，5出栈，同时res[5] = 6-5, 此时栈中还有元素，栈顶值变成2，继续比较。
temperatures[6]大于temperatures[2]，2出栈，同时res[2] = 6-2, 此时栈空，6直接入栈。

p=7时，temperatures[7]小于temperatures[6]，7入栈，stack=[6, 7]

p=8时，越界，退出循环。

此时栈中还有两个元素，它们的等待天数也还是未知的，不过这里稍微想一想就能发现，这两个元素，都是没有找到更高气温的，所以等待天数为0.

代码：

var dailyTemperatures = function(temperatures) {
    let stack = []
    let res = []
    for(let i = 0, len = temperatures.length; i < len; i++) {
        while(stack.length && temperatures[stack[stack.length-1]] < temperatures[i]) {
            let j = stack.pop()
            res[j] = i-j
        }
        stack.push(i)
    }
    //最后栈內存在的元素代表的是在该位置后没有比它更大的值，所以都填0
    while(stack.length) {
        res[stack.pop()] = 0
    }
    return res
}

性能：
时间复杂度：O(n) （不太明白for循环中嵌套了while循环为什么还是O(n)，知道的小伙伴评论里求解答）
空间复杂度：O(n)

屏幕快照 2021-06-02 下午6.00.55.png