Data Structures
Monotonic Stack: The 'Next Greater Element' Pattern
Цели урока
- Understand the 'next greater or smaller' pattern
- Implement a Monotonic Stack in O(n)
- Master the variations: next/previous, greater/smaller
- Solve Largest Rectangle in Histogram
Предварительные знания
- Stacks
The LeetCode problem 'Daily Temperatures' asks, for each day, how many days until it gets warmer. The naive approach is O(n²), but one simple stack trick brings it to O(n). This pattern solves dozens of array problems.
- Market data - the Stock Span Problem
- Weather forecasting - Daily Temperatures
- Computer graphics - the Skyline Problem
- Histogram analysis - Largest Rectangle
From contest folklore to interview staple
The monotonic stack grew out of the competitive programming community rather than a single published paper. Its signature problems took shape over the 1980s and 1990s: Largest Rectangle in Histogram became a standard exercise on the area covered by bars under a skyline, while Next Greater Element and the Stock Span Problem turned the same idea into a reusable scanning template. The pattern stayed mostly oral tradition, passed between contest participants, until the rise of interview preparation sites in the 2010s collected these problems together. There the monotonic stack was recognized as one underlying technique: keep a stack whose values stay sorted, and pop entries the moment an incoming element makes them obsolete. Today it appears in problems from Daily Temperatures to Trapping Rain Water, all variations on finding the nearest larger or smaller element in linear time.
The Problem: Next Greater Element
**The task:** for each element, find the next greater element to its right.
**Naive solution:** for each element, scan to the right, which is O(n²). But we can do it in O(n).
The Next Greater Element for arr=[3,1,2] is:
The Idea: A Monotonically Decreasing Stack
**Invariant:** keep a stack of element indices ordered so that their values decrease from bottom to top.
**Why O(n)?** Each element is pushed once and popped at most once, so the total work is at most 2n operations.
A monotonically decreasing stack maintains:
Implementing Next Greater Element
**Template:** iterate, then while the current value beats the stack top, pop and record the answer, then push the current index.
When does an element get its value written into result?
Variations: Smaller, Previous, Circular
| Problem | Stack | Direction |
|---|---|---|
| Next Greater | Decreasing | Left to right |
| Next Smaller | Increasing | Left to right |
| Previous Greater | Decreasing | Right to left |
| Previous Smaller | Increasing | Right to left |
The Previous Smaller Element problem needs:
Classic Problems
**Largest Rectangle in Histogram** is a LeetCode classic, solved with a monotonic stack in O(n).
- **Daily Temperatures** - how many days until it gets warmer?
- **Stock Span** - how many consecutive days the price stayed at or below today's
- **Trapping Rain Water** - how much water collects between the bars
- **Largest Rectangle in Histogram** - the maximum area
A Monotonic Stack fits problems of the type:
Monotonic Stack
- A stack whose elements stay in monotonic order
- Decreasing stack → Next Greater Element
- Increasing stack → Next Smaller Element
- Iterating right to left → Previous element
- O(n) time: each element is pushed and popped once
Array patterns
Monotonic Stack is one of the core array patterns. Others include Two Pointers, Sliding Window, and Prefix Sum. Combining them solves most array problems.
- Stacks — The base structure for a Monotonic Stack
Связанные уроки
- ds-03-stacks — Builds the pattern directly on top of a plain stack
- alg-26-two-pointers — Both achieve O(n) by never revisiting elements
- alg-27-sliding-window — Sliding window similarly amortizes work to O(n)
- alg-03-amortized — Each element is pushed and popped once, an amortized bound
- ds-14-heaps-intro — Heaps are an alternative for running min/max queries
- alg-36-prefix-sum