84. [✔][H]柱状图中最大的矩形

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

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

示例 1:

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

示例 2：

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

提示：

• 1 <= heights.length <=105
• 0 <= heights[i] <= 104

---

题解：

动画演示 单调栈 84.柱状图中最大的矩形

这个挺难的。

这个结果就是分别计算某一个柱子的左边界(左边第一个比他小的元素)和右边界(右边第一个比他小的元素)。

维护单调递增栈是方便找到栈顶元素左边的第一个边界，而不断循环直到第一个比栈顶元素小的，就是栈顶元素的右边界。

一旦确定左右边界，栈顶元素就可以计算其包含的区域面积。在所有里面找最大值就行。

// @lc code=start
function largestRectangleArea(heights: number[]): number {
    let stack: number[] = [];
    let maxArea = 0;
    let newArray = [0, ...heights, 0];

    for (let i = 0; i < newArray.length; i++) {
        // 如果栈不为空且当前考察的元素值小于栈顶元素值，
        // 则表示以栈顶元素值为高的矩形面积可以确定
        while (stack.length > 0 && newArray[i] < newArray[stack[stack.length - 1]]) {
            // 弹出栈顶元素
            let curIndex = stack.pop()!;//当前需要为中心的柱子索引

            let curHeight = newArray[curIndex];//当前需要为中心的柱子索高度

            let leftIndex = stack[stack.length - 1];//当前需要为中心的柱子左边界(也就是第一个比他小的柱子索引)

            let rightIndex = i;//当前需要为中心的柱子右边界(也就是第一个比他小的柱子索引)

            // 矩形宽度
            let width = (rightIndex - leftIndex + 1) - 2;//减去的2是左右两个边界宽度

            maxArea = Math.max(maxArea, curHeight * width);
        }

        stack.push(i);
    }

    return maxArea;

};
// @lc code=end