84. 柱状图中最大的矩形 困难

问题：

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

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

示例 1:

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

示例 2：

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

回答：

维护一个非严格单调递增栈，一旦发现当前柱子高度小于栈中的最后一个柱子高度，依次pop弹出栈中的柱子，并计算面积，比较得到最大的面积

var largestRectangleArea = function(heights) {
    //单调递增栈
    let stack = [];
    //末尾推入一个元素，为了所有的柱子都被使用
    let h = [...heights, 0];
    let max = 0
    for (let i = 0; i < h.length; i++) {
        while (stack.length && h[i] < h[stack[stack.length - 1]]) {
            let height = h[stack.pop()];
            let width = stack.length == 0 ? i : i - stack[stack.length - 1] - 1;
            max = Math.max(max, height * width)
        };
        stack.push(i)
    }
    return max;
};