Daily LeetCode 739. Daily Temperatures

https://leetcode.com/problems/daily-temperatures/

Medium

问题描述：

Given a list of daily temperatures T, return a list such 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 of temperatures T = [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].

分析：

给定气温序列，求解第i天需要过几天才能升温，实际上就是寻找数组右边第一个比当前元素大的元素。

最开始我的想法是使用暴力解法解决这题，我们只需要从当前元素的位置向右遍历，记录下遇到的第一个比当前元素大的元素位置即可，但这种方法会导致超时。

我们改用栈来解决这个问题，初始化一个栈，==栈中记录当前元素对应的index==。对气温序列进行正序遍历，当栈顶元素小于当前气温时，说明找到了当前栈顶元素右边第一个较大的元素，我们记录当前元素位置即可。

具体来说：

current_stack: [0], res: [0, 0, 0, 0, 0, 0, 0, 0]
current_stack: [1], res: [1, 0, 0, 0, 0, 0, 0, 0] #在index=1时，找到了74，大于73，因此res[0] = 1
current_stack: [2], res: [1, 1, 0, 0, 0, 0, 0, 0] 
current_stack: [2, 3], res: [1, 1, 0, 0, 0, 0, 0, 0]
current_stack: [2, 3, 4], res: [1, 1, 0, 0, 0, 0, 0, 0]
current_stack: [2, 5], res: [1, 1, 0, 2, 1, 0, 0, 0]
current_stack: [6], res: [1, 1, 4, 2, 1, 1, 0, 0]
current_stack: [6, 7], res: [1, 1, 4, 2, 1, 1, 0, 0]

代码：

class Solution(object):
    def dailyTemperatures(self, T):
        """
        :type T: List[int]
        :rtype: List[int]
        """
        stack = []
        res = [0] * len(T)

        for index, value in enumerate(T):
            while stack and value > T[stack[-1]]:
                top = stack.pop()
                res[top] = index - top

            stack.append(index)

        return res