Monotonic Stack: Problem-Solving Framework and Classics

Essence of Monotonic Stack

A monotonic stack maintains its elements in a strictly monotonic order (either strictly increasing or decreasing).

Core Logic: When a new element is about to be pushed, all elements currently in the stack that violate the monotonic property are popped.

Use Cases: Problems that require finding the "Next Greater/Smaller Element" or the "First Greater/Smaller Element on the Left" efficiently (often optimizing O(n²) to O(n)).

Framework: Next Greater Element (Template)

int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Arrays.fill(res, -1);         // Default to -1 if no greater element is found
    Deque<Integer> stack = new ArrayDeque<>();  // Store indices
    
    for (int i = 0; i < n; i++) {
        // Current element is larger than the top, so it is the "Next Greater Element" for the top index
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            int idx = stack.pop();
            res[idx] = nums[i];
        }
        stack.push(i);
    }
    return res;
}

The stack stores indices of elements that are waiting to find their "Next Greater Element" (candidates), maintaining a decreasing order.

Problem Examples

Next Greater Element I (LeetCode 496)

int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Map<Integer, Integer> map = new HashMap<>();   // key: element, value: next greater element in nums2
    Deque<Integer> stack = new ArrayDeque<>();
    for (int x : nums2) {
        while (!stack.isEmpty() && x > stack.peek()) {
            map.put(stack.pop(), x);
        }
        stack.push(x);
    }
    // nums1 elements are a subset of nums2
    return Arrays.stream(nums1).map(x -> map.getOrDefault(x, -1)).toArray();
}

Daily Temperatures (LeetCode 739)

int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] res = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();  // Store indices
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int prevIdx = stack.pop();
            res[prevIdx] = i - prevIdx;   // Distance = current index - popped index
        }
        stack.push(i);
    }
    return res;
}

Circular Array: Next Greater Element II (LeetCode 503)

Handling cycles: Iterate through the array twice (or use modulo arithmetic).

int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Arrays.fill(res, -1);
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < 2 * n; i++) {            // Iterate through two loops
        int x = nums[i % n];
        while (!stack.isEmpty() && x > nums[stack.peek()]) {
            res[stack.pop()] = x;
        }
        if (i < n) stack.push(i);                 // Push into stack only during the first pass
    }
    return res;
}

Harder Challenges: Histograms and Trapping Water

Trapping Rain Water (LeetCode 42)

Intuition: The water level at each column = min(max_left, max_right) - current_height.

Monotonic Stack Approach (Horizontal Calculation):

int trap(int[] height) {
    int res = 0;
    Deque<Integer> stack = new ArrayDeque<>();  // Decreasing monotonic stack
    for (int i = 0; i < height.length; i++) {
        while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
            int bottomIdx = stack.pop();        // The bottom of the valley
            if (stack.isEmpty()) break;
            int leftIdx = stack.peek();
            int w = i - leftIdx - 1;            // Width of the current row being trapped
            int h = Math.min(height[leftIdx], height[i]) - height[bottomIdx]; // Trapped height
            res += w * h;
        }
        stack.push(i);
    }
    return res;
}

Largest Rectangle in Histogram (LeetCode 84)

int largestRectangleArea(int[] heights) {
    int n = heights.length;
    int[] newH = new int[n + 2];  // Add sentinel '0' at both ends to simplify boundary logic
    System.arraycopy(heights, 0, newH, 1, n);
    int res = 0;
    Deque<Integer> stack = new ArrayDeque<>();  // Increasing monotonic stack
    for (int i = 0; i < newH.length; i++) {
        while (!stack.isEmpty() && newH[i] < newH[stack.peek()]) {
            int h = newH[stack.pop()];
            int w = i - stack.peek() - 1;
            res = Math.max(res, h * w);
        }
        stack.push(i);
    }
    return res;
}

Monotonic Stack vs. Prefix Max

Summary

Monotonic Stack Rules of Thumb:

1. Before pushing, pop all elements violating monotonicity. Record answers during the pop operations.
2. The stack stores "elements awaiting a result" (waiting for a larger/smaller neighbor).
3. For Circular Arrays, process the array twice.
4. Use sentinel nodes (e.g., 0 or INT_MAX) at array boundaries to avoid redundant stack-empty checks.