Lesson 9.3 · Stack and Monotonic Stack

The Monotonic Stack

Keep indexes on a stack whose values decrease from bottom to top. Each new element pops every smaller one, and is their "next greater element".

16 min

Think of it like this

People queue at a viewpoint, each wanting to know who is the next taller person behind them in the queue. When a tall person arrives, everyone shorter at the back of the queue gets their answer and leaves. Whoever remains is still waiting for someone taller.

1.Why it's O(n)

The naive way scans right from every index looking for something bigger: O(n²). With the monotonic stack, every index is pushed once and popped at most once, so the total work is O(n), even though there's a while inside the for.

The stack stores indexes, not values, so you can write answers into the right position (or compute distances like "days until warmer").

▶ Dry run: Next greater elementnums = [2, 1, 2, 4, 3]

↑i

stack (indexes)(stack)

0 (2)

answer(list)

-1-1-1-1-1

Step 1/5Push index 0. Answers start as −1 (no greater element).

2.Choosing the direction and comparison

Next greater: keep a decreasing stack and pop while the current value is greater. Next smaller: keep an increasing stack and pop while the current value is smaller. Previous greater/smaller: the element left on the stack after popping is the answer for the current index.

Use > versus >= deliberately when there are equal values: it decides whether equal elements count as "greater".

NextGreater.java

import java.util.*;

public class Main {
    static int[] nextGreater(int[] nums) {
        int[] ans = new int[nums.length];
        Arrays.fill(ans, -1);
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) ans[stack.pop()] = nums[i];
            stack.push(i);
        }
        return ans;
    }
    public static void main(String[] args) {
        System.out.println(Arrays.toString(nextGreater(new int[]{2, 1, 2, 4, 3})));
    }
}

Output

[4, 2, 4, -1, -1]

Quick check

How would you find, for each element, the previous smaller element?

Remember

Store indexes on the stack.
Each index is pushed once and popped once: O(n).
Decreasing stack → next greater; increasing stack → next smaller.
Think carefully about > versus >= for duplicates.

Common mistakes

Storing values instead of indexes, losing where to write the answer.
Using an if instead of a while when popping.

Command Palette

The Monotonic Stack

1.Why it's O(n)

2.Choosing the direction and comparison