Monotonic Stack

Monotonic Stack Introduction

A monotonic stack is a stack that maintains elements in either strictly increasing or strictly decreasing order.

Types

1. Monotonic Decreasing: Top is smallest element
2. Monotonic Increasing: Top is largest element

Why It Works

When we encounter an element that violates the monotonic property, we pop elements and process them. Each element is pushed and popped at most once.

Time Complexity

O(n) - each element is pushed and popped at most once.

When to Use

• Next greater element
• Next smaller element
• Largest rectangle in histogram
• Daily temperatures
• Stock span problem

Monotonic Stack Problems

1. Next Greater Element (LeetCode 496)

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Map<Integer, Integer> map = new HashMap<>();
    Deque<Integer> stack = new ArrayDeque<>();
    
    for (int num : nums2) {
        while (!stack.isEmpty() && stack.peek() < num) {
            map.put(stack.pop(), num);
        }
        stack.push(num);
    }
    
    int[] result = new int[nums1.length];
    for (int i = 0; i < nums1.length; i++) {
        result[i] = map.getOrDefault(nums1[i], -1);
    }
    return result;
}
// Time: O(n), Space: O(n)

2. Daily Temperatures (LeetCode 739)

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] result = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();
    
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
            int prevIndex = stack.pop();
            result[prevIndex] = i - prevIndex;
        }
        stack.push(i);
    }
    return result;
}
// Time: O(n), Space: O(n)

3. Largest Rectangle in Histogram (LeetCode 84)

public int largestRectangleArea(int[] heights) {
    Deque<Integer> stack = new ArrayDeque<>();
    int maxArea = 0;
    int n = heights.length;
    
    for (int i = 0; i <= n; i++) {
        int currentHeight = (i == n) ? 0 : heights[i];
        while (!stack.isEmpty() && heights[stack.peek()] > currentHeight) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    return maxArea;
}

Template

// Next Greater Element (Decreasing Stack)
for (int i = 0; i < n; i++) {
    while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
        int index = stack.pop();
        result[index] = i;  // or arr[i]
    }
    stack.push(i);
}

// Next Smaller Element (Increasing Stack)
for (int i = 0; i < n; i++) {
    while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
        int index = stack.pop();
        result[index] = i;  // or arr[i]
    }
    stack.push(i);
}