You are given temperatures, the temperature on each of a run of days, in order.
Return a list answer of the same length, where answer[i] is how many days after day i the
first strictly warmer day comes. If no later day is warmer, answer[i] is 0.
Example 1
- Input
- temperatures = [70, 68, 72, 71, 69, 75]
- Output
- [2, 1, 3, 2, 1, 0]
Example 2
- Input
- temperatures = [50, 50, 50]
- Output
- [0, 0, 0]
Constraints
temperaturesholds 1 to 10⁵ values.- Every temperature is between 30 and 100.
Show the pattern
Monotonic stack
For every day you want the next later day that beats it: a "next greater item" question. The days still waiting for an answer form a stack of falling temperatures, and each new day pops every waiting day it beats.
See monotonic stack in a visualiserShow the approach
Scan the days with a stack of the indices still waiting for a warmer day. Their temperatures never rise from the bottom of the stack to the top, because a warmer day would already have answered every cooler day below it.
For each new day, pop every waiting day that is cooler than it, and set that day's answer to the difference between the two indices. Then push the new day. Days still on the stack at the end keep the answer 0. Each day is pushed once and popped at most once, so the scan is linear.
Time: O(n) · Space: O(n)