739.Daily Temperatures

Given a list of dailytemperatures, 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, put0instead.

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

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

Method 1 Stack, O(n) time, O(W) # of increasing temperatures in the list.

• Maintain a stack of highest temperature -> lowest temperature from end of the list to beginning.
• Loop through the list of temperatures from end to start, append the index to the stack.
• If the current temperature is greater than the last temperature added into the stack, pop the stack until stack is empty or the last temperature of the stack is greater than the current termperature.
• If stack is not empty, set the current date's next terperature to stack[-1] - i.

class Solution(object):
    def dailyTemperatures(self, temperatures):
        res = [0] * len(temperatures)
        stack = []
        for i in xrange(len(temperatures)-1, -1, -1):
            while stack and temperatures[i] >= temperatures[stack[-1]]:
                stack.pop()
            if stack:
                res[i] = stack[-1] - i
            stack.append(i)
        return res