Monotonic Stack (Daily Temperatures, Rain Water, Histogram)

Core Concept of Monotonic Stack

Maintain a strictly increasing or decreasing stack. When a new element violates the monotonic property, pop elements from the stack and process them.

• Monotonic Decreasing Stack: Elements from bottom to top are in decreasing order. Used to find the Next Greater Element (the first larger element to the right).
• Monotonic Increasing Stack: Used to find the Next Smaller Element.

Daily Temperatures (LeetCode 739)

For each day, find how many days you have to wait until a warmer temperature.

int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] answer = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();  // Store indices, maintain decreasing order

    for (int i = 0; i < n; i++) {
        // Current temperature is higher than the top, so it is the warmer day for the top index
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int idx = stack.pop();
            answer[idx] = i - idx;
        }
        stack.push(i);
    }
    return answer;
}

Next Greater Element II (LeetCode 503)

Next greater element in a circular array:

int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Arrays.fill(res, -1);
    Deque<Integer> stack = new ArrayDeque<>();

    // Iterate twice to simulate a circular array
    for (int i = 0; i < 2 * n; i++) {
        while (!stack.isEmpty() && nums[i % n] > nums[stack.peek()]) {
            res[stack.pop()] = nums[i % n];
        }
        if (i < n) stack.push(i); // Push into stack only during the first pass
    }
    return res;
}

Trapping Rain Water (LeetCode 42)

Monotonic Stack Approach (Calculates horizontal layers):

int trap(int[] height) {
    int water = 0;
    Deque<Integer> stack = new ArrayDeque<>();  // Monotonic decreasing stack

    for (int i = 0; i < height.length; i++) {
        while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
            int mid = stack.pop(); // The bottom of the current horizontal layer
            if (stack.isEmpty()) break;
            int left = stack.peek();
            int h = Math.min(height[left], height[i]) - height[mid]; // Layer height
            int w = i - left - 1; // Layer width
            water += h * w;
        }
        stack.push(i);
    }
    return water;
}

Two Pointers Approach (More concise, highly recommended):

int trapTwoPointer(int[] height) {
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (left < right) {
        leftMax = Math.max(leftMax, height[left]);
        rightMax = Math.max(rightMax, height[right]);
        
        // The side with the lower maximum height determines the water level
        if (leftMax < rightMax) {
            water += leftMax - height[left++];
        } else {
            water += rightMax - height[right--];
        }
    }
    return water;
}

Largest Rectangle in Histogram (LeetCode 84)

Monotonic Increasing Stack: When the current height is smaller than the top, calculate the area using the popped height:

int largestRectangleArea(int[] heights) {
    // Add sentinels (height 0) at both ends to simplify boundary handling
    int n = heights.length;
    int[] h = new int[n + 2];
    System.arraycopy(heights, 0, h, 1, n);
    // h[0] = h[n+1] = 0 by default

    Deque<Integer> stack = new ArrayDeque<>();
    int maxArea = 0;

    for (int i = 0; i < h.length; i++) {
        // When current height 'shrinks', settle the rectangles in the stack
        while (!stack.isEmpty() && h[i] < h[stack.peek()]) {
            int height = h[stack.pop()];
            int width = i - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    return maxArea;
}

Key Tip: When a height is popped, its width extends from the index after the new top to the current index minus 1. This represents the maximum width possible for that specific height.