Stack • Advanced Architecture

Monotonic Stack

A Monotonic Stack is a stack whose elements are guaranteed to be in a strictly increasing or strictly decreasing order. It is the holy grail for "Next Greater/Smaller" problems.

The Pushing Rule

If you want a Monotonic Decreasing Stack, and you try to push `10` onto a stack whose top is `5`, you MUST pop the `5` first. You keep popping until the top is `> 10`, then you push `10`.

The "Aha!" Moment

Every time you pop an element because a new element forced it out, that new element is exactly the Next Greater/Smaller Element for the item being popped! This turns O(N^2) brute force into O(N).

Common Problems

Next Greater Element (Decreasing Stack)
Next Smaller Element (Increasing Stack)
Largest Rectangle in Histogram
Trapping Rain Water
Daily Temperatures

Loading Lab...

Stack • Advanced Architecture

Monotonic Stack

A Monotonic Stack is a stack whose elements are guaranteed to be in a strictly increasing or strictly decreasing order. It is the holy grail for "Next Greater/Smaller" problems.

The Pushing Rule

If you want a Monotonic Decreasing Stack, and you try to push `10` onto a stack whose top is `5`, you MUST pop the `5` first. You keep popping until the top is `> 10`, then you push `10`.

The "Aha!" Moment

Every time you pop an element because a new element forced it out, that new element is exactly the Next Greater/Smaller Element for the item being popped! This turns O(N^2) brute force into O(N).

Common Problems

Next Greater Element (Decreasing Stack)
Next Smaller Element (Increasing Stack)
Largest Rectangle in Histogram
Trapping Rain Water
Daily Temperatures