LeetCode #739 Daily Temperatures

Posted on | Post modified | In , , , , , ,

Problem

Given a list of daily temperatures, 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, put 0 instead.

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

Solution

Method: Stack

Time Complexity: O(n)

Space Complexity: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """
        table = [0 for _ in temperatures]
        stack = [(temperatures[0], 0)]

        for idx, temperature in enumerate(temperatures):
            while stack and temperature > stack[-1][0]:
                table[stack[-1][1]] = idx - stack[-1][1]
                stack.pop()
 
           stack.append((temperature, idx))
            
        return table