Back to DSA

Largest Rectangle in Histogram

hard
Acceptance: 40%
StackMonotonic StackArray

You have a histogram described by an array of bar heights (each bar has width 1). Determine the area of the largest axis-aligned rectangle that fits entirely within the histogram.

Examples

Example 1:
Input:heights = [3,1,6,5,2,4]
Output:10
Example 2:
Input:heights = [1,3]
Output:3

Hints

Related Problems

Min StackmediumValid ParentheseseasyEvaluate Reverse Polish NotationmediumDaily TemperaturesmediumNext Greater Element Ieasy
00:00
import java.util.*;

class Solution {
    public int largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<>();
        int maxArea = 0;
        for (int i = 0; i <= heights.length; i++) {
            int h = (i == heights.length) ? 0 : heights[i];
            while (!stack.isEmpty() && h < heights[stack.peek()]) {
                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;
    }
}
Time complexityO(n)
Space complexityO(n)