You are given a list called temperatures, one temperature per day. For each day, work out how many days you must wait until a strictly warmer day. If no warmer day ever comes, put 0.
Read the first few by hand. Day 0 is 73, and day 1 is 74, which is warmer, so the wait is 1. Day 2 is 75. Days 3, 4 and 5 are all cooler. Day 6 is 76, the first warmer day, so the wait is 6 - 2 = 4. Day 6 is never beaten, so its answer is 0.
There are up to 100,000 days, and each temperature is between 30 and 100.
For each day, find the next day to its right with a bigger value. This question has a name: next greater element. It is the single most useful idea in this group of problems.
From each day, scan forward until you find a warmer day.
python
def dailyTemperatures(temperatures): n = len(temperatures) answer = [0] * n for i in range(n): for j in range(i + 1, n): if temperatures[j] > temperatures[i]: answer[i] = j - i break return answer
If the temperatures keep falling, every scan runs to the end, which is O(n^2). For 100,000 days that is about five billion steps.
The waste in one sentence: a long stretch of cool days gets scanned again and again, once for every earlier day that is waiting to be beaten.
Turn it around. Instead of each day looking forward for its answer, let each new day resolve the earlier days that were waiting for it.
Walk forward through the days. Keep a list of the days that are still waiting for a warmer day. When today arrives, look at the waiting days. Every one that is cooler than today has just found its answer: it is today. Remove those days and write down their waits. Then add today to the waiting list, because today is now waiting for something warmer than itself.
Here is a useful fact about that waiting list. The temperatures in it always go down from the oldest to the newest. Why? Suppose a warmer day arrived while a cooler day was waiting. The cooler day would be resolved straight away and removed. So a cooler day can never be sitting behind a warmer day that came later.
Because the newest waiting days are always the coolest, today only has to check the newest waiting day first. If today beats it, remove it and check the next newest. As soon as today fails to beat one, it cannot beat any older one either, because the older ones are even warmer. So we always work from the newest end. That makes the waiting list a stack.
A stack whose values always go in one direction like this is called a monotonic stack. "Monotonic" means "always moving one way". Here the values always decrease from the bottom of the stack to the top.
A monotonic stack does its useful work when an item is popped, not when it is pushed. The pop is the moment you learn something: "this waiting day has just found its warmer day, and it is today." If you ever find yourself trying to work out an answer at push time, you have the model backwards.
(1) Fill the answer with 0s. Any day that never finds a warmer day should end with 0. By starting every slot at 0, those days are already correct, and we will never need a clean-up step at the end.
(2) The stack of waiting days. It holds positions, not temperatures. The answer is a number of days, which is a difference between two positions. A temperature alone cannot give you that. When we need a waiting day's temperature, we look it up with temperatures[position].
(3) Walk forward through the days.i is today's position and temp is today's temperature.
(4) Does today beat the newest waiting day?stack[-1] is the top of the stack, the newest waiting day. If its temperature is lower than today's, today resolves it. The while keeps going, because today may resolve several waiting days in a row.
We use <, not <=. The problem says strictly warmer. A day with the same temperature does not count, so the earlier day keeps waiting.
(5) Pop the resolved day.j is its position.
(6) Write down its wait. The warmer day is today, at position i, so the wait is i - j days.
(7) Today starts waiting. After resolving everything it can, today goes onto the stack. It is cooler than or equal to everything still below it, so the stack still goes down from bottom to top.
(8) Done. Days still on the stack never found a warmer day, and they already hold 0 from line (1).
Time. There is a while inside a for, but it is not O(n^2). Follow one position through its whole life.
It is pushed onto the stack exactly once, at line (7).
It is popped at most once, at line (5). Once popped, it never comes back.
So over the whole run there are at most n pushes and at most n pops. That is at most 2n stack operations in total, not per turn. Everything else is constant work per day. So the time is O(n).
This is the same "count the total, not the per-turn work" argument as in 4.4.9 and 4.6.6. You will be asked for it every time you use a monotonic stack.
Space. The answer list has n slots. In the worst case, the temperatures only fall, like [100, 90, 80]. Then nothing is ever popped and the stack holds all n positions. So the space is O(n).
Next Greater Element I and II. The same code. In version II the list wraps around in a circle. Walk the list twice, and use i % n to turn a position in the second lap back into a real position. The % sign means "remainder after dividing".
Online Stock Span. How many days in a row, ending today, had a price at or below today's? That is "next greater on the left".
Largest Rectangle in Histogram. Needs the next smaller bar on both sides. That is 4.8.7, the hardest problem in this group.
Remove K Digits. Make the smallest number by deleting k digits. When a smaller digit arrives, pop larger digits before it. Same machinery, different goal.
"Why is this O(n)?" Each position is pushed once and popped at most once.
"Why store positions and not temperatures?" The answer is a distance between positions.
"What is left on the stack at the end?" Days that never found a warmer day. They are already 0.
"Change it to find the next cooler day." Flip < to > in line (4). Doing this without pausing shows you understood the structure.
"Could you walk right to left instead?" Yes. Then the stack holds future days that could be the answer, and you read each day's answer from the top of the stack instead of writing it at pop time. Both are O(n). Left to right is easier to explain, because the pop carries the meaning.
One thing to volunteer: say the rule as one sentence before coding. "A cooler earlier day is resolved the moment a warmer day arrives, so the stack only holds days still waiting, in falling order."
Next:4.8.6 Car Fleet. A physics puzzle that turns out to be the same idea in disguise.