Largest Rectangle in Histogram

Largest Rectangle in Histogram

23%

Accepted

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.

Have you met this question in a real interview? 

Yes

Example

Given height = [2,1,5,6,2,3],
return 10.

public class Solution {
    /**
     * @param height: A list of integer
     * @return: The area of largest rectangle in the histogram
     */
    public int largestRectangleArea(int[] height) {
        // write your code here
        if(height == null || height.length == 0) return 0;
        Stack<Integer> stack = new Stack<Integer>();
        int i = 0, maxArea = 0;
       
        while(i < height.length){
            if(stack.isEmpty() || height[i] >= height[stack.peek()]){
                stack.push(i);
                i++;
            } else{
                int h = height[stack.pop()];
                int wid = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, wid*h);
            }
        }
       
        while(!stack.isEmpty()){
            int h = height[stack.pop()];
            int wid = stack.isEmpty() ? i : i - stack.peek() - 1;
            maxArea = Math.max(maxArea, wid*h);
        }
        return maxArea;  
    }
}