How Does a Monotonic Stack Find the Next Greater Value?
A monotonic stack keeps unresolved indexes in decreasing-value order. Each later value resolves every smaller value on top.
For each position, the next greater value is the first later value that is strictly larger. A stack stores indexes whose answers are still unresolved. Values at those indexes are non-increasing from bottom to top.
Implementation
Press Run to execute this example. Use console.log to print a value.
For [2, 1, 2, 4, 3], index 1 resolves at the later 2. The first 2 does not resolve there because greater is strict; both 2s resolve at 4. The final stack indexes keep the initialised answer -1.
Correctness and cost
Before each input index, the stack contains exactly unresolved earlier indexes, in increasing index order and non-increasing value order. When current pops an index, every value between that index and current was no larger, or the index would already have been popped. Therefore current is its first strictly greater value.
Each index is pushed once and popped at most once. Total time is O(n), despite the inner while, and the answers plus stack use O(n) space.
Edge cases and mistakes
- Equal values do not resolve one another; use
<, not<=. - Store indexes, not only values, because answers belong to positions.
- An empty input returns an empty output.
- A decreasing input leaves every answer at
-1. pop()returnsundefinedon an empty TypeScript array, so guard the stack length.
Optional enrichment
Change the comparison and traversal direction to derive next smaller, previous greater, and previous smaller variants. State the new monotonic invariant each time.