题目描述
有一个直方图,用一个整数数组表示,其中每列的宽度为1,求所给直方图包含的最大矩形面积。比如,对于直方图[2,7,9,4],它所包含的最大矩形的面积为14(即[7,9]包涵的7×2的矩形)。

给定一个直方图A及它的总宽度n,请返回最大矩形面积。保证直方图宽度小于等于500。保证结果在int范围内。

测试样例:

[2,7,9,4,1],5

返回:

14

1 1 收藏


直接登录
最新评论
  • camper   04/18

    能直接想到的方法,高度离散化处理+动态规划,复杂度o(N^2),不知道有没有更快的方法

  • abc2529   04/19

    测试一下。

  • YHT   04/20

    需求没有理解错的话,可以通过四步求解:

    第一步。求连续两个的差,这个差构成一个数组。

    第二步。在这个数组范围内求最小值。这个最小值对应的连续两个柱就构成了面积最大。再这两个柱中再取最小值。

    第三步。根据总宽度和柱状数求平均宽度。先用long存储计算结果。

    第四部,第三步的值和int.maxValue比较。

  • 豪满   04/21

     

  • 小心   04/21

    二分法思路:

    1.找到最小的高度 面积=最小高度*数组长度

    2.根据最小高度将数组分割成两部分,根据第一步求面积

    3.循环第二部

    4.找到最大值