题目

---

给一个每日温度数组，代表每一天的温度，返回一个数组，代表每一天最快需要几天后可以回暖（温度比当天温度高），若不存在回暖的一天，则为0。

例如：

• 输入为：temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
• 输出为：[1, 1, 4, 2, 1, 1, 0, 0]
• 因为：第一天温度为73°F，需要等一天即可回暖（74），第二天同样。第三天75°F，需要等4天后76°才能回暖。

注意：温度范围是[30, 100]

解法

---

1. 暴力 （超时）

每一天都查找之后的温度，直到找到比这一天温度高的

class Solution(object):
    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """
        result = []
        for i, t in enumerate(temperatures):
            for j, h in enumerate(temperatures[i:]):
                if h > t:
                    result.append(j)
                    break
            else:
                result.append(0)
        return result

2. 记录温度下标

维持一个数组nxt，以温度为下标，以出现日期为值。从后向前遍历温度数组T，过程中，记下每一个温度最新出现的位置（即日期最早）到nxt中，并查找其中温度高于当天温度的最早出现日期，由于是从后向前遍历，所以所得日期一定大于当前日期。

class Solution(object):
    def dailyTemperatures(self, T):
        nxt = [float('inf')] * 102
        ans = [0] * len(T)
        for i in xrange(len(T) - 1, -1, -1):
            #Use 102 so min(nxt[t]) has a default value
            warmer_index = min(nxt[t] for t in xrange(T[i]+1, 102))
            if warmer_index < float('inf'):
                ans[i] = warmer_index - i
            nxt[T[i]] = i
        return ans

3. 堆栈

把气温做出折线图，好像一座座山峰，我们要求的就是在某一点上所能看到的比他更高的山峰。从后向前遍历温度数组，在栈中记录所能看到的山峰，看不到的部分出栈。

山峰类比

也就是说，栈中保存的温度是从栈顶到栈底依次递增的。每遍历到一个新温度，都把比自己温度低的出栈。相当于删去被挡住的山。

class Solution(object):
    def dailyTemperatures(self, T):
        ans = [0] * len(T)
        stack = [] #indexes from hottest to coldest
        for i in xrange(len(T) - 1, -1, -1):
            while stack and T[i] >= T[stack[-1]]:
                stack.pop()
            if stack:
                ans[i] = stack[-1] - i
            stack.append(i)
        return ans