Friday, January 17, 2014

Largest Rectangle in Histogram (Java)

LeetCode

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 height = [2,1,5,6,2,3],
return 10.

Solution:
Maintain a stack which used to record bar's indexes, in order to reach max increasing  bars until an shorter bar come,  then we calculate the  area of each situation consist by the bars in our stack. Because there may a coupe bars left in our stack, so don't forget calculate  them after first while loop.