Why This Matters
Monotonic stacks solve "next greater", "previous smaller", temperatures, stock span, and histogram boundary problems in linear time. The trick is not memorizing templates; it is seeing which candidates are permanently dominated.
The invariant is an ordered stack of unresolved candidates.
Prerequisite Check
Review Arrays and Stacks. You should be comfortable pushing and popping indices, not just values, because most problems need positions.
Learning Objectives
By the end, you should be able to:
- Define increasing and decreasing stack invariants.
- Explain why popped candidates never need to return.
- Implement next-greater-element to the right.
- Adapt the method to previous-smaller boundaries.
- Avoid confusing value order with index order.
Core Idea
Scan once. Before pushing the current element, pop stack entries that the current element resolves or dominates.
| Pattern | Invariant | Typical problem |
|---|---|---|
| Decreasing stack | stack values decrease from bottom to top | next greater element |
| Increasing stack | stack values increase from bottom to top | next smaller element |
| Boundary stack | indices remain candidates for left/right limits | largest rectangle in histogram |
| Span stack | popped values are covered by current value | stock span, daily temperatures |
Visual Model
values: [2, 1, 5]
stack before 5: indices [0, 1] with values [2, 1]
5 pops 1 and 2 because it is their next greater value
Every index is pushed once and popped at most once.
Non-Example or Failure Mode
A monotonic stack is not helpful when every old item can remain relevant after a larger or smaller value appears. If no dominance rule lets you discard candidates, the stack invariant is fake.
Worked Example
For [2, 1, 5, 3], next greater values are:
2 -> 5
1 -> 5
5 -> none
3 -> none
When 5 arrives, it resolves both 1 and 2. Later 3 cannot resolve 5, so it stays unresolved.
LeetCode-Style Problem Patterns
| Pattern | Recognition signal | Move |
|---|---|---|
| Next greater/smaller | "first value to the right greater than..." | pop while current resolves top |
| Daily temperatures | wait until warmer day | decreasing stack of indices |
| Histogram rectangle | nearest smaller boundary | increasing stack with sentinel |
| Stock span | count consecutive dominated prices | pop smaller/equal prices |
Common Mistakes
| Mistake | Correction |
|---|---|
| Storing values when duplicates matter. | Store indices so positions and equal values are handled correctly. |
| Using the wrong inequality. | Decide whether equal values should pop before coding. |
| Forgetting unresolved entries. | Leave them as None, -1, or problem-specific default. |
| Claiming every stack is monotonic. | The stack must preserve a value-order invariant. |
Diagnostic Questions
| Question type | Question | Answer signal |
|---|---|---|
| Definition | What makes the stack monotonic? | Its unresolved candidates remain in increasing or decreasing value order. |
| Example / non-example | Is a normal parentheses stack monotonic? | No; it stores nesting structure, not ordered candidates. |
| Computation | Why is next-greater linear? | Each index is pushed once and popped at most once. |
| Proof | Why can a popped index be discarded forever? | The current element is the first future element that resolves it. |
| Transfer | How does the histogram problem use the same idea? | Smaller bars define boundaries that resolve taller bars. |
Exercises
Beginner:
- Trace next greater element for
[4, 1, 2, 7, 3]. - Decide whether daily temperatures needs an increasing or decreasing stack.
- Explain why indices are safer than values.
Intermediate:
- Implement previous smaller element.
- Add duplicate-value tests and choose strict or non-strict comparison.
Challenge:
- Implement largest rectangle in histogram using a monotonic stack and sentinel bar.
Diagram Recommendation
Type: candidate-elimination trace.
Caption: "A new value pops every unresolved candidate it dominates."
Purpose: Show why the same elements do not get rescanned.
Implementation Task
Implement next greater element to the right. Keep stack as indices whose answers are not known yet.
Run monotonic stack next-greater
This cell computes next greater values and checks duplicate-sensitive cases.
Output will appear here.
Next Topics
References
- MIT OpenCourseWare. 6.006 Introduction to Algorithms, Spring 2020: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
- Princeton Algorithms, Stacks and Queues: https://algs4.cs.princeton.edu/13stacks/
- Python documentation, lists as stacks: https://docs.python.org/3/tutorial/datastructures.html#using-lists-as-stacks