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 =
return
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.
No comments:
Post a Comment