📊

Monotonic Increasing Stack

Maintain indices in increasing height order. When height[i] < height[stack.top()], pop and compute area = height × width (width = distance to previous smaller bar). A sentinel 0 at end flushes all remaining bars. O(n) — each bar pushed/popped once.

Histogram Rectangle Area Monotonic Stack Time O(n) Space O(n)

📋 When to Use

Largest rectangle in histogram
Maximal rectangle in 2D binary matrix
Find previous / next smaller element for any bar
Any "pop when current is smaller" scenario
Trapping rain water variant using stack

💡 Key insight: the stack always holds indices in strictly increasing height order. A smaller incoming bar acts as the "right boundary" for every taller bar being popped — giving us both height and width in O(1).

⚡ Complexity

Time

O(n)

Space

O(n)

Each index is pushed onto the stack exactly once and popped at most once — so total work is O(2n) = O(n) even with the inner while loop.

Sentinel 0 guarantees all bars are processed — no post-loop cleanup needed.

Input heights = [2, 1, 5, 6, 2, 3] → sentinel 0 appended → h = [2, 1, 5, 6, 2, 3, 0]

Step 0 / 0

🔍 Scan 📥 Push 💥 Pop+Area 🏆 New Max! 🏁 Done

Histogram (heights proportional, sentinel shown as dashed)

📚 Stack

bottom → top (left → right)

empty

Area Computation

— waiting for pop —

maxArea:0

i =—

h[i] =—

Press Play or Next to start the animation.

for (int i = 0; i < h.length; i++) { ... }

Pattern SkeletonJava

// Monotonic Increasing Stack — Largest Rectangle
Deque<Integer> stack = new ArrayDeque<>();
int maxArea = 0;
// Sentinel 0 at end ensures all bars are flushed
int[] h = Arrays.copyOf(heights, heights.length + 1);

for (int i = 0; i < h.length; i++) {
    while (!stack.isEmpty() && h[i] < h[stack.peek()]) {
        int height = h[stack.pop()];
        // Width = distance to previous smaller element
        int width = stack.isEmpty() ? i : i - stack.peek() - 1;
        maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
}
return maxArea;

📌 Practice Problems

#84 Largest Rectangle in Histogram Hard #85 Maximal Rectangle Hard #42 Trapping Rain Water Hard #907 Sum of Subarray Minimums Medium