Monotonic Stack

Foundations

So far, the stack held items in arrival order, and each entry carried what later steps needed. Now, what if each element is waiting for the first later element that beats it, and one new arrival can settle several waiting elements at once?

A monotonic stack keeps the waiting elements in falling order from bottom to top. When a new element arrives, it pops every smaller element on top, because it is the first larger value each of them has met, and then it is pushed to wait itself. Each element is pushed once and popped at most once, so a loop that looks nested does O(n) work in total.

On nums = [7, 1, 5, 3, 6], find each element's next greater value. The 7 and the 1 wait, in falling order. Then 5 pops 1, so 1's answer is 5, and 5 waits above 7; 3 waits above 5. Finally 6 pops 3 and then 5, answering both, and stops at 7, which is larger. Nothing beats 7 or 6, so their answers stay empty.

Case Scenario

Daily Temperatures is the next greater element with days for indexes: temperatures[i] is day i's reading, and the answer for day i is how many days later a warmer one comes, j - i, or 0 if none does. In temperatures = [73, 74, 75, 71, 69, 72, 76, 73], day 2 (temperatures[2] = 75) waits until day 6 (temperatures[6] = 76), so answer[2] = 4.

The direct approach scans forward from each day until it finds a warmer one: an outer loop picks day i, and an inner loop checks days i + 1 onward. When temperatures only fall, every scan runs to the end, n(n - 1)/2 checks in all. Step through the days below to see how often the same later days get read again.