Stack · LC #739
Daily Temperatures
For each day find how many days until a warmer temperature, using a monotonic decreasing stack of indices to solve in O(n) time.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given an array of integers `temperatures` representing daily temperatures, return an array `answer` such that `answer[i]` is the number of days you have to wait after the `i`-th day to get a warmer temperature. If there is no future day with a warmer temperature, `answer[i] = 0`.
Sample I/O
Input: temperatures = [73,74,75,71,69,72,76,73] Output: [1,1,4,2,1,1,0,0] Input: temperatures = [30,40,50,60] Output: [1,1,1,0] Input: temperatures = [30,60,90] Output: [1,1,0]
Time: O(n) · Space: O(n)
Intuition
How to Think About It
Intuition
The key insight is to process each temperature "lazily" - instead of searching forward for a warmer day when we visit index i, we wait until we find a warmer day later and resolve all waiting indices at that point. A monotonic decreasing stack stores indices of temperatures that are still "waiting" for a warmer day.
Core Concept
Maintain a stack of indices in decreasing order of their temperatures. For each new temperature at index i, pop all indices from the stack whose temperature is strictly less than the current temperature - each popped index idx gets answer `i - idx`. Then push i. Any indices remaining in the stack at the end had no warmer future day and keep their default answer of 0.
When to use
Next Greater Element pattern: find the next element to the right that is greater (or smaller) than the current. Any "next warmer/larger/smaller" problem on an array.
When NOT to use
When you need the nearest greater element to the left (use left-to-right scan with increasing stack). When the condition is non-strict (>=) or multi-criteria.
Key Insights
What to Know Cold
- Store indices, not values, in the stack so you can compute the distance `i - idx` and fill `res[idx]`.
- Each element is pushed exactly once and popped at most once → amortized O(1) per element → O(n) total.
- Stack is monotonically decreasing in temperature value - invariant maintained by the while-pop loop.
- Default-initializing the result array to 0 means you never need to write 0 explicitly for unresolved indices.
- This is the canonical "Next Greater Element" template used in many harder stack problems.
1 example
Worked Examples
Trace on [73,74,75,71,69,72,76,73]
Walk through the stack state and show when each index gets resolved.
i=0: push 0. i=1: 74>73, pop 0 (res[0]=1), push 1. i=2: 75>74, pop 1 (res[1]=1), push 2. i=3: 71<75, push 3. i=4: 69<71, push 4. i=5: 72>69, pop 4 (res[4]=1); 72>71, pop 3 (res[3]=2); push 5. i=6: 76>72, pop 5 (res[5]=1); 76>75, pop 2 (res[2]=4); push 6. i=7: 73<76, push 7. End: 6,7 remain → res[6]=res[7]=0.
dailyTemperatures([73,74,75,71,69,72,76,73]); // Returns: [1, 1, 4, 2, 1, 1, 0, 0]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
Index 2 (temp=75) waits 4 days until index 6 (temp=76) - shows that a single push can resolve many waiting indices in one pass, proving the O(n) bound.