739. Daily Temperatures

Medium

Problem:

Given a list of daily temperatures in Fahrenheit ('F) T, output how many more days one would have to wait for a warmer day.

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

The seventh and eighth days no longer have warmer days, so they are both 0.

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

Solution:

Stack

1. Keep stacking the current index

2. At a point where it rises compared to before, compare the temperature difference between the current temperature and the temperature at the index point stacked in the stack.

3. If the current temperature is higher, then pop the value from the stack and treat the difference between the current index and the stacked index as the answer.

Similar stack technique: 42. Trapping Rain Water 🔥

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer = [0] * len(temperatures)
        stack = []

        for i, cur in enumerate(temperatures):
            while stack and cur > temperatures[stack[-1]]:
                last = stack.pop()
                answer[last] = i - last
            stack.append(i)
        return answer

Time Limit Exceeded

class Solution:
    def dailyTemperatures(temperatures: List[int]) -> List[int]:
        stack = temperatures
        answer = []
        while len(stack) > 0:
            count = 1
            popped = stack.pop(0)
    
            for idx, temp in enumerate(stack):
                if popped >= temp:
                    # [55, 38, 53, 81, 61, 93, 97, 32, 43, 78] -> popped: 97
                    if idx == (len(stack) - 1) and count == idx + 1:
                        answer.append(0)
                        break
                    count = count + 1
                elif popped < temp:
                    answer.append(count)
                    break
                if len(stack) == 1:
                    answer.append(0)
                    break
        answer.append(0)
        return answer