Stacks & Queues/Practice/Daily Temperatures
Daily Temperatures - Monotonic Stack Walkthrough
Walk the days left to right keeping a stack of "days still waiting for a warmer temperature", always in decreasing temperature order. When today is warmer than the day on top of the stack, pop it and record the gap. Repeat, then push today.
Why it works
Every day is pushed once and popped at most once, so the total work is O(n) - even though each day may wait on the stack. The decreasing order is the trick: any day on the stack colder than today can never be answered by anything except today.
The problem
Given an array temperatures, return an array answer where answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day with a warmer temperature, set answer[i] = 0.
Hints
- Maintain a stack of indices where temperatures are decreasing.
- When you find a warmer temp, pop indices from the stack and compute the wait.
- answer[stack.pop()] = current_index - popped_index
Test cases
| Input | Expected |
|---|---|
daily_temperatures([73,74,75,71,69,72,76,73]) | [1,1,4,2,1,1,0,0] |
daily_temperatures([30,40,50,60]) | [1,1,1,0] |
Reference starter code
def daily_temperatures(temperatures):
# Monotonic decreasing stack stores indices
pass
print(daily_temperatures([73,74,75,71,69,72,76,73])) # [1,1,4,2,1,1,0,0]
print(daily_temperatures([30,40,50,60])) # [1,1,1,0]
print(daily_temperatures([30,60,90])) # [1,1,0]
More challenges in this topic
Try it yourself
Solve it in the browser editor with real test cases and instant feedback - free, no signup needed.