LC739. Daily Temperatures

Approach 1: Monotonic Stack

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = [0]
        res = [0] * len(temperatures)
 
        for i, t in enumerate(temperatures):
            # Start going back when we find a day warmer than the day
            # on top of the stack
            while stack and t > temperatures[stack[-1]]:
                prevIdx = stack.pop()
                res[prevIdx] = i - prevIdx
            
            stack.append(i)
        
        return res

Complexity

Time: $O(N)$ — each element has one associated pop with it so O(2 \cdot N) \approx O(N)$$. Space: O(n)$

Notes

Other Languages