Largest Rectangle in HistogramApr 23 '12
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 =
return
Given height =
[2,1,5,6,2,3],return
10.
This comment has been removed by the author.
ReplyDeletelines 13 through 17 is magic! One possible explanation for the formula in line 16 is as follows:
ReplyDelete(1) If we carefully look at line 11, each and every element of height is pushed once into the stack. So, when do we push indx into the stack ?
We push for the conditions in (1.a) and (1.b) as explained below.
- (1.a) When the stack is empty which will be EITHER when indx = 0 OR when the following happens: For all i < indx, height[i] > height[indx] in which case we will need to drain the entire stack (lines 13-17) before pushing indx. i.e, if the bottom most element of the stack is not 0, say 4, height[0],height[1],height[2],height[3] are all greater than height[4].
- (1.b) when stack is non-empty and height[indx] >= height[i]. Note that when this happens, EITHER indx is i+1 OR indx is i+k (k > 1) where
height[i+1], height[i+2]...height[indx-1] are all greater than height[indx]. Why is this always true? It simply follows from the logic that we will not push an element indx into the stack until we drain all i where height[i] > height[indx] from the stack. i.e for a non-empty stack with stack[top] = 8 and stack[top+1] = 5, we can safely conclude that height[8] > height[5] and most importantly, height[6] > height[8] and height[7] > height[8].
2. Using (1.a) and (1.b) the formula in line 16 is fairly straightforward. The formula can be split into 2 cases (2.a) and (2.b) as described below:
(2.a). From (1.a) we can deduce the following if histStack has only 1 element while reaching line 14. : height[0], heights[1]...height[histStack.top()] are > height[indx]. Hence the width of the largest possible rectangle is indx-histStack.top(). This is the formula for line 16 for histStack with one element.
(2.b) For histStack with atleast 2 elements when we reach line 14. Consider histStack at any arbitrary point of time while entering line 14 to be 0 1 3 5 8. =>
height[0] <= height[1] <= height[3] <= height[5] <= height[8].
For the top 2 adjacent entries in histStack, i.e top = 8 and top+1 = 5, height[8] >= height[5]. Now height[8] > height[5], height[6] > height[8] and height[7] > height[8] from the logic in (1.b). What does this imply? If we fix indx as the right index, for height[histStack.top()], the furthest left index where height[leftIndex] >= height[histStack.top()] is histStack[histStack.top()+1]+1. Hence the formula for the atleast 2 elements in stack in line 16.
Combining (2.a) and (2.b) gives us the required formula in line 16.