现在的位置: 首页 > 综合 > 正文

一道小米的关于柱状图求最大矩阵面积的题

2013年03月10日 ⁄ 综合 ⁄ 共 281字 ⁄ 字号 评论关闭

题目描述:

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

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

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

抱歉!评论已关闭.