Day60题目
60天打卡最后一天
LeetCode84柱状图中最大面积
核心思想:当当前遍历到的元素小于栈顶元素的时候,此时栈顶元素最大面积就是自身面积,然后while向左移动,如果左边的值大于当前遍历到的元素,可以得到中间两个的元素最大矩形面积(左边的高度*2)
理解了下面这个用例,就能理解
[2,3,4,1,1,1,1,1,1,1,1,1,1,1,1]
/**
* @param {number[]} heights
* @return {number}
*/
var largestRectangleArea = function (heights) {
var res = 0
var stack = []
heights = [0, ...heights, 0];
for (let i = 0; i < heights.length; i++) {
while (heights[stack[stack.length - 1]] > heights[i]) {
let mid = stack.pop();
let h = heights[mid];
let w = i - stack[stack.length-1] - 1;
res = Math.max(res, h * w);
}
stack.push(i)
}
return res;
};