Card 08/ 08
Recap: Monotonic Stack
Indices wait on a stack in sorted order of value, and each new value answers the ones it beats, in O(n) for the whole array.
A monotonic stack holds the positions still waiting for an answer, kept in sorted order of value, and each new value pops and answers every waiting position it beats. Every index is pushed once and popped at most once, so the whole pass is O(n) time and O(n) extra space, whatever the inner loop does on a single step. The variants differ in three places:
| Variant | Stack order (bottom to top) | Pop when | Answer read | Loop |
|---|---|---|---|---|
| Next greater | Decreasing | The top's value is smaller than the current one | For the popped index | i from 0 to n − 1 |
| Next smaller | Increasing | The top's value is larger than the current one | For the popped index | i from 0 to n − 1 |
| Previous greater | Decreasing | The top's value is smaller than the current one | For the current index, from the top left after popping | i from 0 to n − 1 |
| Circular next greater | Decreasing | The top's value is smaller than the current one | For the popped index | i from 0 to 2n − 1, value at i mod n, push only while i < n |
Store indices whenever the answer is a distance or a position; a value is always one read away through its index, while an index cannot be recovered from a value that repeats. Positions never popped have no answer, so the answer array starts filled with −1, or 0 for a wait. Strictly larger or smaller is decided by the comparison: < leaves equal values waiting, and <= lets them answer each other.
← → move through sections and cards