#739
Daily Temperatures
Medium Monotonic stack of indexes
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
For each day, return how many days you must wait for a warmer temperature, or 0 if none comes.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: for each day, how many days until a warmer one?
Why this works: a stack of waiting days (cooler ones on top). A warmer day pops them and fills in their wait.
Example: [73, 74, 75, 71, 69, 72, 76]
74 answers 73 (1), 75 answers 74 (1)72 answers 69 (1) and 71 (2)76 answers 72 (1) and 75 (4)
✦Hints open one at a time
Keep a stack of day indexes still waiting for a warmer day.
The stack's temperatures are decreasing from bottom to top.
↗Approach
For each day i, while today is warmer than the day on top of the stack, pop it and set its answer to i − thatDay. Push i.
</>Solution (Java)
import java.util.*;
class Solution {
public int[] dailyTemperatures(int[] temps) {
int[] ans = new int[temps.length];
Deque<Integer> stack = new ArrayDeque<>(); // indexes, decreasing temps
for (int i = 0; i < temps.length; i++) {
while (!stack.isEmpty() && temps[stack.peek()] < temps[i]) {
int day = stack.pop();
ans[day] = i - day;
}
stack.push(i);
}
return ans;
}
}!Common mistake
Storing temperatures instead of indexes — you need the index to compute the wait.
Complexity
- Time: O(n) — each index is pushed and popped once.
- Space: O(n).
Topic: Stack & Queue
🎬 Episodes 46–52: video coming soon