Largest Rectangle in Histogram

Hard

Python

def largest_rectangle_area(heights):
    stack=[]; max_area=0
    for i,h in enumerate(heights+[0]):
        while stack and heights[stack[-1]]>h:
            ht=heights[stack.pop()]
            w=i if not stack else i-stack[-1]-1
            max_area=max(max_area,ht*w)
        stack.append(i)
    return max_area

Java

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

Key Insight

Python appends sentinel 0. Java uses loop condition. Identical logic.

Python → Java Differences

Python heights+[0] sentinel
Java i==heights.length check
Monotonic stack identical

Python

def largest_rectangle_area(heights):
    stack=[]; max_area=0
    for i,h in enumerate(heights+[0]):
        while stack and heights[stack[-1]]>h:
            ht=heights[stack.pop()]
            w=i if not stack else i-stack[-1]-1
            max_area=max(max_area,ht*w)
        stack.append(i)
    return max_area

Java

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

Algorithm Steps

1. Monotonic increasing stack
2. Pop when shorter found
3. Calculate area

← Previous All Stacks & Queues