0
Challenge · 36Structures You Build Yourself
Monotonic stack
Structuresused in ~70% of apps
The one pattern in this tier that does not look like anything you have seen. It answers "what is the next bigger thing to my right" for every position at once, in a single pass, and the first time you meet it, it looks like magic.
Core idea. Keep a stack whose values only ever increase (or only ever decrease) from bottom to top. Anything that would break that order gets popped off, and the moment a value is popped, the item that pushed it out <em>is</em> its answer.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
Playground, this isn't a screenshot
next greater element, [2, 1, 4, 3]
2stack [2]nothing to pop. Push 2
1stack [2, 1]1 < 2, still decreasing. Push
4stack [4]1 → 42 → 44 beats both. Each gets its answer
3stack [4, 3]3 < 4. Push, still waiting
, stack []4 → none3 → noneend: whatever remains has no answer
The stack always reads decreasing from bottom to top. The moment that would break, somebody gets their answer.
↑ play a little first, then dig in