Monotonic Stack: Daily Temperatures Drill
Finding the next greater value in a time series naively requires $O(N^2)$ nested loops. A Monotonic Stack preserves indices in strictly decreasing order. When a warmer temperature arrives, it pops smaller elements from the stack and calculates index differences in amortized $O(N)$ linear time 🌡️📈⚡.
def next_warmer(temps):
res = [0] * len(temps)
stack = [] # Index stack
for i, t in enumerate(temps):
while stack and t > temps[stack[-1]]:
prev = stack.pop()
res[prev] = i - prev
stack.append(i)
return res
print("Days to wait:", next_warmer([70, 72, 68, 75]))
# 21. Monotonic Stack: Daily Temperatures Drill Whenever you encounter questions asking for the "next greater element", "previous smaller element", or "largest rectangle under a histogram", nested loops ($O(N^2)$) will fail performance tests. The optimal tool is a **Monotonic Stack** 🛑. ```python # The Monotonic Decreasing Stack Flow: # Temps: [73, 74, 75, 71, 69, 72] # Day 0 (73): Stack = [0] # Day 1 (74): 74 > 73 -> Pop 0! Wait time for day 0 is (1 - 0) = 1 day. Stack = [1] # Day 2 (75): 75 > 74 -> Pop 1! Wait time for day 1 is (2 - 1) = 1 day. Stack = [2] # Day 3 (71): 71 < 75 -> Push 3. Stack = [2, 3] # Day 4 (69): 69 < 71 -> Push 4. Stack = [2, 3, 4] # Day 5 (72): 72 > 69 -> Pop 4! Wait time for day 4 is (5 - 4) = 1. # 72 > 71 -> Pop 3! Wait time for day 3 is (5 - 3) = 2. # 72 < 75 -> Push 5. Stack = [2, 5] ``` ### Amortized $O(N)$ Proof Even though there is a `while` loop inside the `for` loop: - Each index enters the stack at most once. - Each index leaves the stack at most once. - Maximum total stack operations across the entire algorithm is $2N$. - Performance: Pure **$O(N)$ linear time** 🌡️📈⚡! --- ### Interactive Pop-Quiz 🧠 #### Why is the time complexity of the monotonic stack algorithm strictly O(N) despite having a while loop nested inside a for loop? - [ ] Because every index is pushed onto the stack exactly once and popped at most once across the entire algorithm execution ($2N$ operations) 📈 - [ ] Because Python skips the while loop during compilation - [ ] Because monotonic stacks execute in GPU memory - [ ] Because array lengths are capped at 100 elements --- ### Practical Challenge 🎯 Implement `daily_temperatures(temperatures: list[int]) -> list[int]`. For each day, compute the number of days you must wait until a warmer temperature occurs (or 0 if no warmer day exists). Test with `[73, 74, 75, 71, 69, 72, 76, 73]`, assert `[1, 1, 4, 2, 1, 1, 0, 0]`, and print result. <details> <summary>Solution</summary> ```python def daily_temperatures(temperatures: list[int]) -> list[int]: n = len(temperatures) answer = [0] * n stack = [] for curr_day, curr_temp in enumerate(temperatures): while stack and curr_temp > temperatures[stack[-1]]: prev_day = stack.pop() answer[prev_day] = curr_day - prev_day stack.append(curr_day) return answer temps = [73, 74, 75, 71, 69, 72, 76, 73] result = daily_temperatures(temps) assert result == [1, 1, 4, 2, 1, 1, 0, 0] print(f"Monotonic stack verified: {result}") ``` </details>