算法随笔_35: 每日温度

上一篇:算法随笔_34: 最后一个单词的长度-CSDN博客

=====

题目描述如下:

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

=====

算法思路:

这道题的暴力解法是，我们从左往右枚举temperatures[i]，对于每一个temperatures[i]，我们用第二层循环再枚举它之后的元素，从而找到temperatures[i]的第一个更高的温度。第一层循环完成后，即可返回答案。

接下来我们探讨一个更高效的算法，单调栈解法。为了方便描述，下面我们用tp代替temperatures数组，res表示answer数组。我们用一个示例来解析一下算法背后的原理。我们假设tp有15个元素。让我们从左往右开始枚举数组。

1.  如果tp[1]大于tp[0]，我们就找到了tp[0]的答案。

2.  如果tp[1]小于tp[0]，我们需要查看tp[2]，如果tp[2]大于tp[1]，此时我们就找到了tp[1]的答案为tp[2]。

3.  如果tp[2]也大于tp[0]，那么我们也找到了tp[0]的答案为tp[2]。

经过上面这3步的分析，我们发现当温度连续递减的时候，这些被访问过的元素都还没找到它们对应的答案。当递减之后温度第一次升高时如tp[5]。我们可以从右往左对于访问过的元素tp[0]，tp[1]，tp[2]，tp[3]，tp[4]再一次比较。此时可以依次找到部分元素的答案，直到tp[5]小于某个已经访问过的元素为止。

根据此特征，我们可以使用单调栈的思路来解决此问题。具体的算法如下:

1.  我们设一个临时数组stck做为单调栈，stck初始元素为0。设结果数组res，它的长度和tp数组一样，初始每个元素为0。然后从左往右枚举数组tp。

2.  如果温度保持递减趋势，我们把元素下标不断的放入数组stck中，直到碰到第一次升高，比如tp[i]。

3.  我们用tp[i]和stck的末尾元素，即stck[-1]，比较。如果stck[-1]小于元素tp[i]，我们计算两个下标的距离，并存入res数组对应的位置。然后弹出stck[-1]。重复步骤3，直到碰到stck[-1]大于tp[i]，我们把下标i放入stck中。

4. 继续枚举tp[i+1]，转到步骤3。直到枚举完数组tp。

如果stck中仍有元素，说明这些元素不能找到更高的温度。相应的res位置因为初始值就为0，所以无需处理这些元素。

此算法的时间复杂度为O(n) 。下面是代码实现:

class Solution(object):
    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """
        tp_len=len(temperatures)
        stck=[0]
        res=[0]*tp_len
        for i in range(1,tp_len):
            while len(stck)>0 and temperatures[i]>temperatures[stck[-1]]:
                res[stck[-1]]=i-stck[-1]
                stck.pop()
            stck.append(i)
            
        return res