84. Largest Rectangle in Histogram
题目描述
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.
题目大意
给定一数组代表直方图的矩形条高度,每个矩形条的宽度为1,在直方图种找到最大矩形的面积,如上图中例子所示。
解题思路
遍历矩形条高度,计算以当前矩形条为高度的最大面积(即要维持一个递增序列)
使用Stack构建递增序列,比栈顶小的值则弹出,并计算其面积,否则压栈。
代码
|
|