Daily Temperatures
Find how many days you have to wait for a warmer temperature.
MediumSolve on LeetCode
Problem Understanding
temperatures[i] is the temperature on day i. Build an array answer where answer[i] counts the days from day i until the first strictly warmer day. If no warmer day ever comes, answer[i] stays 0.
Algorithm Strategy
We use a Monotonic Decreasing Stack.
- Initialize
answerarray with 0s. - Use a stack to store indices of days.
- Iterate through
temperatures. - While the current temperature is warmer than the temperature at the index stored in
stack.top():- We found a warmer day for
stack.top()! - Pop the index (
prevIndex). - Calculate days waiting:
i - prevIndex. - Update
answer[prevIndex].
- We found a warmer day for
- Push current index
ionto the stack.
Interactive Visualization
Visualize how the monotonic stack keeps track of 'unresolved' cooler days.
Dry Run
Input: [73, 74, 75, 71, 69, 72]
| Day | Temp | Stack (Indices) | Action |
|---|---|---|---|
| 0 | 73 | [0] |
Push 0 |
| 1 | 74 | [] -> [1] |
74 > 73. Pop 0. ans[0] = 1-0 = 1. Push 1. |
| 2 | 75 | [] -> [2] |
75 > 74. Pop 1. ans[1] = 2-1 = 1. Push 2. |
| 3 | 71 | [2, 3] |
71 < 75. Push 3. |
| 4 | 69 | [2, 3, 4] |
69 < 71. Push 4. |
| 5 | 72 | [2] -> [2, 5] |
72 > 69 (Pop 4). 72 > 71 (Pop 3). Push 5. |
Edge Cases & Common Mistakes
- Decreasing Order:
[90, 80, 70]. Stack just grows. Output all 0s. - Stack Contents: Remember to store indices, not values.
Solution
Monotonic Stack O(N).
Daily Temperatures Code
1var dailyTemperatures = function(temperatures) {2 const n = temperatures.length;3 const answer = new Array(n).fill(0);4 const stack = []; // indices56 for (let i = 0; i < n; i++) {7 while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {8 const idx = stack.pop();9 answer[idx] = i - idx;10 }11 stack.push(i);12 }13 return answer;14};