Monotonic Stack Basics

Monotonic stacks are a powerful pattern for solving “next greater/smaller element” problems in linear time. They show up in questions about:

  • Next greater element.
  • Daily temperatures / stock span.
  • Largest rectangle in a histogram.
  • Sliding window maximum (with a monotonic queue).

If your brute‑force solution scans left/right neighbors for each element to find a greater or smaller element, a monotonic stack is usually the right optimization.

What Is a Monotonic Stack?

A monotonic stack is a stack that maintains its elements in increasing or decreasing order (by some key) as you push and pop while scanning an array.

Two main variants:

  • Monotonically increasing stack:
    • Elements from bottom to top are non‑decreasing.
    • Useful for “next greater element” problems.
  • Monotonically decreasing stack:
    • Elements from bottom to top are non‑increasing.
    • Useful for “next smaller element” or some max problems.

The trick: when you see a new element, you pop from the stack while the monotonic property is violated, and treat the popped elements as having found their next greater/smaller neighbor.

Example: Next Greater Element to the Right

Problem:

Given an array nums, for each index i find the next index j > i such that nums[j] > nums[i]. If no such index exists, return -1.

Naive solution: nested loops → O(n²).

Monotonic stack solution (scan from right to left):

Java
int n = nums.length;
int[] ans = new int[n];
Arrays.fill(ans, -1);
Deque<Integer> stack = new ArrayDeque<>(); // store indices, stack is increasing by value

for (int i = n - 1; i >= 0; i--) {
    while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
        stack.pop();
    }
    if (!stack.isEmpty()) {
        ans[i] = stack.peek(); // index of next greater element
    }
    stack.push(i);
}

Key points:

  • Stack stores indices, not values.
  • At each i, we pop all indices with nums[stack.top] <= nums[i] because they cannot be the next greater element for anything to the left of i.
  • Each index is pushed and popped at most once → O(n) total work.

Intuition: Why Is It O(n)?

Think of the stack as a list of “candidates” that are still waiting for a greater element to their right.

  • When a new element becomes the next greater for some candidates, they get popped and never return.
  • Any index enters and leaves the stack at most once.

So even though there is a while‑loop inside a for‑loop, the total number of pops is O(n), not O(n²).

Other Common Uses

1. Daily Temperatures / Stock Span

Instead of next greater index, you may want:

  • Number of days until a warmer temperature.
  • How many consecutive days a stock price has been >= current price.

These problems are thin wrappers around the same monotonic stack structure, just with different post‑processing on indices.

2. Largest Rectangle in Histogram

For each bar, you need to know:

  • The first smaller bar to the left.
  • The first smaller bar to the right.

Both can be found with a monotonic increasing stack in O(n), giving width for which a bar is the limiting height.

3. Sliding Window Maximum (Monotonic Queue)

Related idea: maintain a deque that is decreasing by value. As the window moves:

  • Pop from back while new element is greater (keep deque decreasing).
  • Pop from front if it falls out of the window.
  • Front of deque is always the maximum in the current window.

This is essentially a monotonic stack with window semantics.

Design Checklist

When considering a monotonic stack:

  1. Do you need, for each index, the first greater/smaller element to left/right?
  2. Does the naive solution scan far left/right from each index?
  3. Can you process indices in one direction and discard candidates once they are “resolved”?

If yes, a monotonic stack/queue is often the right approach.

Common Pitfalls

  • Wrong comparison operator (< vs <=) leading to duplicates handled incorrectly.
  • Storing values instead of indices, which makes it hard to compute distances or handle equal elements.
  • Forgetting that the stack should store elements in monotonic order from bottom to top.

Always write out a small example and simulate the stack content after each step.

Summary

Monotonic stacks are a simple but powerful pattern:

  • Turn repeated neighbor scans into a single linear pass.
  • Naturally track “yet unresolved” candidates waiting for a greater/smaller element.
  • Generalize to monotonic queues for sliding window extremes.

Learning this pattern well pays off across many array and stack interview problems.