[数据结构与算法]leetcode739.每日温度

题目：

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

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

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

思路：

最直观的解法就是暴力解法了，遍历这个数组，然后遍历到一位的时候，遍历这一位后面的数组，直到找到比当前数大的数，然后下标相减得到输出，但是python肯定会超时的。太暴力了。
这里使用单调栈的思路，

就是放进栈中的一定是递减的，先遍历第一个数，将它的下标放进栈中，注意这里放的是下标，然后循环往后遍历，如果后面遍历到的温度值比当前的栈顶元素对应的温度值大，说明找到比它大的了，大了就不能放进栈中了，我们先让栈顶元素出栈，然后计算两个下标的差值，放在结果列表中，再将当前元素下标放进栈中，继续遍历，如果温度值小于栈顶元素，就直接将下标放进栈中，直到再碰到大于栈顶元素下标对应值的，再出栈。结果列表默认就是0。

class Solution(object):
    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """
        length = len(temperatures)
        ans =[0] * length
        stack = []# 这里存的是下标
        for i in range(length):
            temperature = temperatures[i]
            while stack and temperature > temperatures[stack[-1]]:
                pre = stack.pop()
                ans[pre] = i -pre
            stack.append(i)
        return ans