Monotonic stack
Walk left to right with a stack of items still waiting for a bigger value. Each new item answers everything on top of the stack that it beats, then waits its turn. The stack's values only ever shrink towards the top.
27354618
For every item, find the first bigger value to its right. Press play or step forward to start.
1function nextGreater(a) {2 const answer = new Array(a.length).fill(-1);3 const stack = [];4 for (let i = 0; i < a.length; i++) {5 while (stack.length > 0 && a[stack.at(-1)] < a[i]) {6 answer[stack.pop()] = a[i];7 }8 stack.push(i);9 }10 return answer;11}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n | rising input: each item is answered by the next one |
| average | n | any input |
| worst | n | each index is pushed once and popped at most once |
| space | n | falling input leaves everything on the stack |
Where it breaks
- "A loop inside a loop is n²." Each index goes on the stack once and comes off at most once, so the inner
whileruns at most n times in total. Pick Valley: the 7 and the 9 clear the whole stack between them. - Storing values instead of indexes. The answer has to go back to a position. Push indexes, and look the values up, or duplicates leave you unable to tell which slot to fill.
- Strict or not.
<finds the next strictly greater value. Change it to<=and equal values answer each other, which is a different question.