Leetcode – Largest Rectangle in Histogram Java

Tags: , ,

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.

Analysis

A simple solution is to expand for each bar to its both left and right side until the bar is lower. 

The algorithm is described in this post to calculate the largest area of rectangle. 

Since this algorithm has time complexity O(n^2), we need a faster solution. 

The idea is to scan the bars from left to right.  If a bar is lower than its previous one, we know the previous bar can not be used to form any other rectangles with the future bars, so we can safely expand to the left of current bar, and remove those higher bars before the current bar.   If a bar is higher than its previous one, there is a potentiality that it can be used to form a rectangle with next  bar, so we just continue scan to the right. 

A clearer implementation: