How to Use a Monotonic Stack for Next Greater Element Problems: A Complete Guide

A monotonic stack solves "next greater element" problems in O(N) time by maintaining a strictly decreasing stack while scanning from right to left, popping elements that cannot be answers for future positions.

The monotonic stack is a fundamental pattern in algorithm design, extensively documented in the labuladong/fucking-algorithm repository. This technique efficiently finds the first element that is larger (or smaller) on the right or left of each position, transforming brute-force O(N²) solutions into linear time algorithms.

What Is a Monotonic Stack?

A monotonic stack is a stack data structure that maintains its elements in a monotonic order—either strictly increasing or strictly decreasing—throughout the traversal of a sequence. Unlike a standard stack, elements are actively removed (popped) to preserve this ordering property as new elements arrive.

For next greater element problems, the stack maintains a strictly decreasing sequence of values from bottom to top. This ensures that the top of the stack always represents the nearest candidate that could be the "next greater" element for upcoming positions in the array.

The Core Algorithm Template

The canonical implementation, found in 数据结构系列/单调栈.md at lines 53-71, follows a right-to-left traversal pattern:

1. Traverse from right to left (or left to right for "previous" queries).
2. Maintain a decreasing stack: While the stack is not empty and the top element is less than or equal to the current element, pop the stack.
3. Record the answer: The new stack top (if exists) is the next greater element; otherwise, use -1 (or 0 for distance-based problems).
4. Push current element: Add the current value (or index) to the stack and continue.

This algorithm achieves O(N) time complexity and O(N) auxiliary space because each element is pushed and popped at most once.

// Template implementation from lines 53-71
int[] nextGreater(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Stack<Integer> st = new Stack<>();
    
    for (int i = n - 1; i >= 0; i--) {
        // Maintain decreasing property: pop smaller or equal elements
        while (!st.isEmpty() && st.peek() <= nums[i]) {
            st.pop();
        }
        // Stack top is next greater, or -1 if empty
        res[i] = st.isEmpty() ? -1 : st.peek();
        st.push(nums[i]);
    }
    return res;
}

Solving Next Greater Element Variants

The monotonic stack template adapts to several common problem variations documented in the repository.

Next Greater Element I (Two Arrays)

When finding the next greater element for values in nums1 based on their positions in nums2, first compute the "greater" mapping for nums2 using the monotonic stack, then look up each nums1 element in the resulting map.

The concrete Java adaptation appears at lines 96-114 in 数据结构系列/单调栈.md, utilizing a HashMap to store the precomputed results for O(1) lookups.

Daily Temperatures (Distance Instead of Value)

For problems requiring the distance to the next greater element rather than the value itself, modify the stack to store indices instead of values. The result at position i becomes stack.peek() - i (or 0 if the stack is empty).

The implementation at lines 150-168 demonstrates this pattern:

// Daily Temperatures - store indices, compute distance
int[] dailyTemperatures(int[] temps) {
    int n = temps.length;
    int[] ans = new int[n];
    Stack<Integer> idx = new Stack<>();
    
    for (int i = n - 1; i >= 0; i--) {
        while (!idx.isEmpty() && temps[idx.peek()] <= temps[i]) {
            idx.pop();
        }
        ans[i] = idx.isEmpty() ? 0 : idx.peek() - i;
        idx.push(i);
    }
    return ans;
}

Next Greater Element II (Circular Arrays)

Circular arrays require finding the next greater element with wrap-around behavior. Simulate the doubled array by iterating from 2*n - 1 down to 0, using i % n for indexing, while maintaining a single stack pass.

The efficient implementation at lines 111-120 avoids actually duplicating the array:

// Circular array handling
int[] nextGreaterCircular(int[] nums) {
    int n = nums.length;
    int[] ans = new int[n];
    Stack<Integer> st = new Stack<>();
    
    for (int i = 2 * n - 1; i >= 0; i--) {
        int cur = nums[i % n];
        while (!st.isEmpty() && st.peek() <= cur) {
            st.pop();
        }
        ans[i % n] = st.isEmpty() ? -1 : st.peek();
        st.push(cur);
    }
    return ans;
}

Previous Greater or Smaller Elements

To find previous greater elements (looking left instead of right), reverse the traversal direction to left-to-right. The stack logic remains identical, but answers are recorded for the current index based on the stack state before pushing the current element. For previous smaller elements, invert the comparison operator to >=.

When to Choose a Monotonic Stack

Select a monotonic stack when the problem exhibits these characteristics:

• First occurrence queries: The problem asks for the first element that is larger or smaller in a specific direction (right or left).
• Linear time requirement: The input constraints (typically 10⁵ to 10⁶ elements) preclude O(N²) brute-force solutions.
• Single-pass optimization: Each element only needs to know about its nearest qualifying neighbor, not all possible candidates.

For aggregate queries such as the maximum in a sliding window, a monotonic queue (deque) is the appropriate structure instead, as documented in 数据结构系列/单调队列.md. The distinction lies in whether you need to access elements at both ends (queue) or only the top (stack).

Summary

• A monotonic stack maintains elements in strictly decreasing (or increasing) order to efficiently answer "next greater element" queries.
• The standard template traverses from right to left, popping elements smaller than or equal to the current value, leaving the stack top as the answer.
• The algorithm runs in O(N) time and O(N) space, with each element pushed and popped at most once.
• Common variations include handling circular arrays (simulated doubling), computing distances (storing indices), and finding previous greater elements (left-to-right traversal).
• According to the labuladong/fucking-algorithm repository, the core implementation resides in 数据结构系列/单调栈.md at lines 53-71, with specific adaptations for LeetCode problems at lines 96-114 and 150-168.

Frequently Asked Questions

What is the time complexity of the monotonic stack algorithm?

The monotonic stack algorithm operates in O(N) time complexity and O(N) auxiliary space. Each element in the array is pushed onto the stack exactly once and popped at most once. Because the while-loop only pops elements that will never be needed again, the total number of operations across the entire traversal is linear with respect to the input size.

Can I use a monotonic stack for previous smaller elements?

Yes. To find previous smaller or greater elements, reverse the traversal direction from right-to-left to left-to-right. Maintain the same stack logic, but invert the comparison operator (use >= for previous smaller, <= for previous greater). The answer for the current index is determined by the stack state before you push the current element, as the stack now contains candidates from the left side.

How do I handle circular arrays with a monotonic stack?

For circular arrays where the next greater element can wrap around to the beginning, simulate a doubled array without actually duplicating the data. Iterate i from 2*n - 1 down to 0, and use i % n to index into the original array. Use a single stack pass through this virtual doubled range. This approach, shown at lines 111-120 of 数据结构系列/单调栈.md, correctly identifies next greater elements across the circular boundary while maintaining O(N) time complexity.

What is the difference between a monotonic stack and a monotonic queue?

A monotonic stack is optimized for finding the nearest greater or smaller element in a single direction (left or right), operating solely from the top of the stack. A monotonic queue (typically implemented as a deque) is required when you need to maintain a window of elements and access both ends efficiently, such as in sliding window maximum problems. According to the repository's 数据结构系列/单调队列.md, choose a stack for "next/previous" element queries and a queue for range-based aggregate queries.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}