84. 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.

p1

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

p2

The largest rectangle is shown in the shaded area, which has area = 10 unit.
  • MonotonicStack N
public int largestRectangleArea(int[] h) {
    ArrayDeque<Integer> stack = new ArrayDeque<>();
    stack.push(-1);
    int result = 0;
    for(int i = 0; i < h.length; i++) {
        while(stack.peek() != -1 && h[stack.peek()] > h[i]) {
            int height = h[stack.pop()];
            result = Math.max(result, height * (i - 1 - stack.peek()));
        }
        stack.push(i);
    }
    while(stack.peek() != -1) {
        int height = h[stack.pop()];
        result = Math.max(result, height * (h.length - 1 - stack.peek()));
    }
    return result;
}
  • divede and conquer NlogN

find the lowest bar, divide the histograms into left and right parts. result = max(loestHeight * widthOfTheHistogram, maxOfLeftPart, maxOfRightPart)