原题地址：柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10
暴力计算
计算所有可能的面积，并找出其中的最大值。具体的实现代码如下：
/**
* @param {number[]} heights
* @return {number}
*/
const largestRectangleArea1 = function(heights) {
// 记录最大矩形面积
let max = 0;
// 找出所有可能的矩形面积
for (let i = 0; i < heights.length; i ++) {
// 记录从i开始的矩形的高度
let minHeight = heights[i];
for (let j = i; j < heights.length; j ++) {
// 从i到j的矩形高度为这段区间内所有高度值的最小值
minHeight = Math.min(minHeight, heights[j]);
// 此时的矩形面积为这个高度值与i和j之间距离的乘积
max = Math.max(max, minHeight * (j - i + 1));
}
}
return max;
};
测试：
let start = new Date();
const test = largestRectangleArea1;
console.log(test([2,1,5,6,2,3])); // 10
console.log(new Date().getTime() - start.getTime()); // 8
时间复杂度： 双重遍历，时间复杂度为$O(N^2)$
空间复杂度： 常数级额外空间，空间复杂度为$O(1)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 28,2019