739. Daily Temperatures

Summary

Solution Approach	Explanation (1-minute)	Time Complexity	Space Complexity
Brute Force	For each day, iterate through all subsequent days to find the first day with higher temperature	\(O(n^2)\)	\(O(1)\)
Monotonic Stack	Use a decreasing stack to store (index, temperature) pairs. When a warmer day is found, pop all cooler days from stack and calculate their wait times	\(O(n)\)	\(O(n)\)

Implementation

PythonJavaScriptGo

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        days = [0] * len(temperatures)
        stack: list[tuple[int, int]] = [] # list of pairs = (idx, temp)

        for curr_day, curr_temp in enumerate(temperatures):

            while len(stack) != 0 and stack[-1][1] < curr_temp:
                target_day, _ = stack.pop()
                days[target_day] = curr_day - target_day

            stack.append((curr_day, curr_temp))

        return days

```