84 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]
输出： 4

思路：

首先理解一下题意，想要求能够勾勒出的最大矩形面积

⇒ Math.max(…以单个柱子为高度能够勾勒的最大面积）

如何求单个柱子能够勾勒的？就是找到离这个柱子左右两边最近的比较小的，用left和right标记。如果没有，则right = arr.length -1, left = 0;

⇒ 求左侧第一个比自己小的元素 + 求右侧第一个比自己小的元素

⇒ 使用单调栈即可。

对于上述思路不是很清楚的，可以参考单调栈总结以及Leetcode案例解读与复盘

代码实现：

/*** @param {number[]} heights* @return {number}*/
var largestRectangleArea = function(heights) {// 找出每个元素右边比自己小的let right = new Array(heights.length).fill(heights.length-1);// 找出每个元素左侧比自己小的let left = new Array(heights.length).fill(0);let stack = [];for(let i = 0;i<heights.length;i++){while(stack.length && heights[i] < heights[stack.at(-1)]){right[stack.pop()] = i-1;}left[i] = stack.length ? stack.at(-1)+1 : 0;stack.push(i); }let max = 0;for(let i = 0;i<heights.length;i++){max = Math.max(max, heights[i]*(right[i]-left[i]+1));}return max;};console.log(largestRectangleArea([2,1,5,6,2,3]));