题目描述：

LeetCode 739. Daily Temperatures

Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

题目大意：

给定一组每日温度，求每一天最少需要等多少天可以达到更高的温度

解题思路：

字典minIdx[n]记录达到温度n的最小下标idx

倒序遍历温度列表temperatures，记当前温度为n，更新minIdx，从n + 1到100遍历minIdx，取最小值

Python代码：

class Solution(object):
    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """
        minIdx = collections.defaultdict(int)
        ans = []
        size = len(temperatures)
        for x in range(size - 1, -1, -1):
            n = temperatures[x]
            minIdx[n] = x
            z = 0
            for y in range(n + 1, 101):
                if minIdx[y] and (minIdx[y] < z or not z):
                    z = minIdx[y]
            ans.append(z - x if z else 0)
        return ans[::-1]

 

本文链接：http://bookshadow.com/weblog/2017/12/03/leetcode-daily-temperatures/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码