487. Daily Temperatures
You are given an array temperatures, where temperatures[i] is the temperature recorded on day i. For every day, work out how long its owner has to wait for a strictly warmer day.
Return an array answer of the same length where answer[i] is the number of days from day i until the first later day with a higher temperature — that is, the smallest j > i with temperatures[j] > temperatures[i] gives answer[i] = j - i. If no warmer day ever comes, answer[i] = 0.
A day with an equal temperature does not count as warmer.
Example 1:
Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
Explanation: Day 0 (73°) is answered by day 1 (74°): wait 1. Day 2 (75°) has to wait until day 6 (76°): wait 4. Days 6 and 7 never see anything warmer, so they get 0.
Example 2:
Input: temperatures = [30, 60, 90]
Output: [1, 1, 0]
Explanation: Each day is immediately beaten by the next, except the last day, which has nothing after it.
Constraints:
- 1 ≤ temperatures.length ≤ 10⁵
- 30 ≤ temperatures[i] ≤ 100
Hints:
The direct translation — for each day, scan forward until something warmer appears — is O(n²). Think about all the scanning it repeats: once day j answers day i, no other day's scan needs to re-examine what lies between them.
Keep a stack of days that are still waiting for their answer. When a new temperature arrives, which of the waiting days can it answer? Only those on top with colder temperatures — pop them all and record the distance.
Notice what remains on the stack after every step: temperatures that never increase from bottom to top (a monotonic stack). That's why each day is pushed once and popped at most once, making the whole pass O(n).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Expected output: [1, 1, 4, 2, 1, 1, 0, 0]