题解 题解 | #直方图内最大矩形#
题解 | #直方图内最大矩形#
149 浏览 0 回复 2022-02-22
直方图内最大矩形

一个直方图可以视为多个宽度为1的矩形的紧密相连,每个矩形的高为heights数组中对应的值.这些矩形覆盖了平面上的一个区域,我们要在其中找到一个面积最大的矩形.
暴力搜索
面积最大的矩形的高一定是heights中的某个值,否则矩形可以增高,从而面积扩大.我们遍历每一个高度,对于heights[i],分别向左向右搜索.如果遇到了某个高度小于heights[i