A LIFO structure, ideal for matching/parsing problems and "look back" problems. The monotonic stack keeps the stack increasing or decreasing, popping while the incoming element breaks the order — each pop is the answer for the popped index, which is how next-greater/next-smaller problems get solved in O(n) instead of O(n²).
Sub-patterns
- A — Matching & Parsing. Bracket matching and calculator-style expression parsing.
- B — Monotonic Stack. Next-greater/next-smaller in O(n) by popping while order is broken.
- C — Stack-Based Simulation. Using a stack to directly model a process (encode/decode, collisions, path simplification).
- D — Min-Stack Style Design. Augmenting a stack to answer an extra query (like current minimum) in O(1).
Practice set (13)
- Easy — Valid Parentheses, Baseball Game
- Medium — Min Stack, Daily Temperatures, Evaluate Reverse Polish Notation, Next Greater Element II, Decode String, Asteroid Collision, Online Stock Span, Remove K Digits, Simplify Path
- Hard — Largest Rectangle in Histogram, Basic Calculator
Matching & Parsing
Bracket matching and calculator-style expression parsing — the stack tracks what still needs to be closed or evaluated.
Monotonic Stack
Keep the stack increasing or decreasing; pop while the incoming element breaks the order — each pop is the answer for next-greater/next-smaller, in O(n).
Stack-Based Simulation
Use a stack to directly model a process — string decoding, asteroid collisions, path simplification.
Min-Stack Style Design
Augment a stack so it can answer an extra query — like the current minimum — in O(1) alongside push/pop.
Notes from readers
Comments — via GitHub