柱状图求最大矩形面积

时间:2022-03-25 11:50:54

题目描述:

给一组非负的整数来表示一个柱状图,设计一个算法获得柱状图中最大矩形的面积。比如,输入如下数据:2,1,4,5,1,3,3 ,其中每个数表示一个柱状条的高度,柱状条的宽度为默认值1,则计算得最大矩形的面积为8,如下图所示。

柱状图求最大矩形面积

柱状图求最大矩形面积

思路很简单,以一个柱形为中心往两边扫描,若旁边的柱形高度大于等于该柱形高度,则继续往两边扫。最后记录往旁边扫描了多少距离。比如图中的系列6,它的高度为3,然后往两边扫描,发现系列7高度大于等于它,而系列5小于它。那么总共扫描距离为2(包括自身),故以系列6为中心的矩形面积为3*2=6。

按上述步骤依次算出每个柱形的矩形面积,取最大值。