How long until it gets warmer
MediumStuck?
Show a hintHide the hint
Keep a stack of days still waiting for a warmer one. When today is warmer than the day on top, that day's answer is today.
The ideas behind this problem
Next in this lesson
How long this price has been the bestFor each day, say how many days you must wait for a warmer temperature. If it never gets warmer, the answer for that day is 0.
Worked example#
For [73, 74, 75, 71, 69, 72, 76, 73]:
| day | temp | next warmer day | wait |
|---|---|---|---|
| 0 | 73 | day 1 at 74 | 1 |
| 1 | 74 | day 2 at 75 | 1 |
| 2 | 75 | day 6 at 76 | 4 |
| 3 | 71 | day 5 at 72 | 2 |
| 4 | 69 | day 5 at 72 | 1 |
| 5 | 72 | day 6 at 76 | 1 |
| 6 | 76 | never | 0 |
| 7 | 73 | never | 0 |
So the answer is [1, 1, 4, 2, 1, 1, 0, 0].
The idea#
Checking every later day for each day is a nested loop, which is fine for eight days and far too slow for a hundred thousand.
Instead keep a stack of days that are still waiting for their answer. Walk the temperatures once. For each new day, any waiting day colder than today has just found its warmer day: pop it and record the gap. Then today joins the stack to wait its turn.
Because the stack only ever holds days that are waiting, and every day is pushed once and popped at most once, the whole thing is one pass.
The stack always ends up with its temperatures decreasing from bottom to top. That is worth noticing, because the same shape solves a whole family of "next greater thing" problems.
Constraints#
1 <= n <= 10000030 <= temperatures[i] <= 100
Input
temperatures is a count then that many integers.
Output
A count is not printed. Print the waits, separated by spaces.
Examples
Input
8 73 74 75 71 69 72 76 73
Output
1 1 4 2 1 1 0 0
Day 2 at 75 waits until day 6 at 76, which is four days.
Input
4 30 40 50 60
Output
1 1 1 0
Each day is warmer than the last, so every wait is one, and the last never warms.
Input
3 30 60 90
Output
1 1 0
Rising again, so the same pattern.
Something wrong with this problem? Report an issue
Ready to try it
Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.
Free, and it stays free. No card.