739. Daily Temperatures (Python)

Related Topic

Stack.

Description

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].

Methodology

We can use brutal forch method to iterate each temperature. For each temperature, we will iterate rest temperatures to find one that greater than current and update the days of wait for current will be the difference of index. This method will cost O(n^2). We can do better by using stack. We iterate the T. Each time, When the top of the stack is less than the value of T, we pop out the top of the stack, this will save a lot time because once you pop the top out, you do not need to compare that again. This will roughly give O(2n)

def dailyTemperatures(self, T: List[int]) -> List[int]:
        if not T: return []
        res = [0] * len(T)
        stack = []
        for index, val in enumerate(T):
            while stack and stack[-1][0] < val:
                stack_top_index = stack.pop()[1]
                count = index - stack_top_index
                res[stack_top_index]=count
            stack.append((val, index))
        return res

BigO

Iterate the T once will take O(n) and the worst case will be roughly O(2n)