Largest Rectangle in Histogram

Question

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Analysis

We keep bars in stack with non-descending order.

If now the new incoming bar is lower than the top bar in stack (we call it ori_top), i.e. violates the rule, then we will start clear the stack until the top bar in stack is lower than the new incoming bar.

During the clearance, we noted that each popped bar will be always smaller than (or equal) the pre_top as we defined it follows non-descending order, while the new incoming bar is smaller than those popped bars, so we can guarantee the max rectangle start from each popped ends at ori_top.

Be careful when calculating the length of the popped bar:

stack.isEmpty() ? i : (i-stack.peek()-1)

Solution

public int largestRectangleArea(int[] heights) {
        if(heights==null || heights.length==0) return 0;
        int[] stack=new int[heights.length];
        int max=0, i=0,top=0;
        while(i<heights.length){
            if(top==0 || heights[i]>=heights[stack[top-1]]) stack[top++]=i++;
            else{
                max=Math.max(max,heights[stack[--top]]*(top==0?i:(i-stack[top-1]-1)));
            }
        }
        while(top>0){
            max=Math.max(max,heights[stack[--top]]*(top==0?i:(i-stack[top-1]-1)));
        }
        return max;
    }