84. Largest Rectangle in Histogram

Largest Rectangle in Histogram

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.

For example, Given heights = [2,1,5,6,2,3], return 10.

Solution

public class Solution {
       public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        int size = heights.length;
        heights = Arrays.copyOf(heights, size + 1);

        Stack<Integer> indices = new Stack<>();
        int max = 0;
        for(int i = 0; i < heights.length; i ++) {
            while (!indices.isEmpty() && heights[i] < heights[indices.peek()]) {
                int h = heights[indices.pop()];
                int w = indices.isEmpty() ? i : i - indices.peek() -1;
                max = h*w > max? h*w:max;
            }

            indices.push(i);
        }

        return max;
    }
}