题目:
难度:Hard
相关话题:栈
、数组
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为 [2,1,5,6,2,3]
。
图中阴影部分为所能勾勒出的最大矩形面积,其面积为 10
个单位。
示例:
思路:
利用栈构建一个递增序列,如果存在一个递增序列,例如[1,3,5]
,那么3
这个高度对应的宽度就很好计算了。
举个例子:[2,4,5,3,1]
假设现在stack
为[2,4,5]
,当前是遍历的值是3
;
现在不满足递增序列了,因此pop
,删除5
,那么就要计算删掉的5
它对应的宽度width
。
5
的宽度就是在4
和3
之间的所有索引,也就是idx(3)-idx(4)-1
,相当于i-stack[stack.lenght-1]-1
;
同理,接下来删除4
,4
的宽度就是idx(3)-idx(1)-1
;
栈变为[2,3]
,遇到下一个值1
,继续上面的步骤,当前不能满足递增序列,删3
,删2
;
注意,这里删除2
的时候,由于2
已经是当前栈的最后一个值,因此2
的宽度其实就是idx(1)
,我将初始stack
设置为-1
,也是为了可以继续套用i-stack[stack.lenght-1]-1
。
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
* @param {number[]} heights
* @return {number}
*/
var largestRectangleArea = function(heights) {
let stack=[-1],maxArea=0
for(let i=0;i<=heights.length;i++){
while(stack.length>1 && (i===heights.length || heights[i]<heights[stack[stack.length-1]])){
let lastId=stack.pop(),
lastH=heights[lastId],
width=i-stack[stack.length-1]-1
maxArea=Math.max(maxArea,width*lastH)
}
stack.push(i)
}
return maxArea
};
扩展阅读: