Get max histogram rectangle

By | October 16, 2015
Share the joy

I solved this problem one year ago. This time I solved it again and wrote some analysis for it.

Problem definition:
Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have same width and the width is 1 unit.

For example, consider the following histogram with 6 bars of heights {6, 2, 5, 4, 5, 6}. The largest possible rectangle possible is 12 (see the below figure, the max area rectangle is highlighted in red)

I think this problem has some application background. That is for each number in set of numbers, find farthest continuous left and right of numbers which all larger than the number. For example, for element 3, the right most it can reach is 4, the left most it can reach is element 2.

To solve this problme, stach is used. We should firstly iterate number from left to right by stack by below rules:
1.From left to right
2.If current is smaller than stack top, then pop stack. After pop stack tp, calculate area size for position tp
3.In the end, push current index

Then we pop all element in stack:
1. For each poped element, use arrary.length and stack.peek() to calculate area size.

The process is like below:
From left to right

Pop the rest stack

github: link