Histogram Max Rectangular Area

Time: O(n)

Space: O(n)

Problem Overview

For each bar, find how far left and right it extends as the minimum bar.

Intuition

For each bar, find how far left and right it extends as the minimum bar. Use a monotonic increasing stack: when a shorter bar is found, the popped bar is bounded on the right by the current bar and on the left by the new stack top.

Algorithm

1Stack of indices. Append heights[n]=0 as sentinel.
2For i from 0 to n: while stack not empty and heights[i] < heights[stack.top]:
3 h = heights[stack.pop()]. w = (stack empty) ? i : i−stack.top−1.
4 area = h*w. Update maxArea.
5Push i.

Example Walkthrough

Input: heights = [2,1,5,6,2,3]

1. Process 5,6: pushed. At 2: pop 6 (area=6), pop 5 (area=10). At sentinel: pop 2(area=2*5=10),1(area=6).
2. maxArea=10.

Output: 10

Common Pitfalls

• Append a 0-height bar at the end to flush all remaining bars from the stack.

Histogram Max Rectangular Area.java

Java

// Approach: Monotonic stack. Maintain stack of increasing bar indices; on decrease, pop and compute area.
// Time: O(n) Space: O(n)
class Solution {
    public static int getMaxArea(int arr[]) {
        Stack<Integer> st = new Stack<>();

        int i = 0, max = 0, n = arr.length;

        while (i < n || !st.isEmpty()) {

            if (i < n && (st.isEmpty() || arr[i] > arr[st.peek()]))
                st.add(i++);

            else
                max = Math.max(max, arr[st.pop()] * (st.isEmpty() ? i : i - st.peek() - 1));

        }
        return max;

    }
}

Was this solution helpful?