柱状图中最大的矩形
louzhedong opened this issue · 0 comments
louzhedong commented
习题
出处:LeetCode 算法第84题
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为
[2,1,5,6,2,3]
。图中阴影部分为所能勾勒出的最大矩形面积,其面积为
10
个单位。示例:
输入: [2,1,5,6,2,3] 输出: 10
解答
var largestRectangleArea = function (heights) {
heights.push(0);
var max = 0;
var stack = [[0, -1]];
var top = 0;
heights.forEach(function (height, index) {
var current = index;
while (stack[top][0] > height) {
var [h, i] = stack.pop();
max = Math.max(max, (index - i) * h)
current = i;
top--;
}
if (stack[top][0] < height) {
stack.push([height, current]);
top++;
}
})
return max;
};
Ï