84. Largest Rectangle in Histogram

Leetcode link

题目简介

/**
 * @param {number[]} heights
 * @return {number}
 */

本题给我们一个数字数组 heights，代表连续长方形的高度，每个长方形的宽度都是 1

题目要求我们求出这些长方形能够组成的最大长方形面积是多少

解题思路

本题是一道 hard，所以会有多个难点需要我们一一解决

首先是，我们需要明确一点，能够组成最大长方形面积的高一定是 heights 中存在的高

其次，我们需要解决的问题是，我们要怎么求 heights 中任意高度 height[i] 能组成长方形的面积？

长方形的高度我们确认了，就是 height[i] 本身，那么宽度呢？

我们拿题目中的例子一的图来解释：

假设我们需要求高度为 5 的长方形最大的宽度，我们需要找到左右第一个比当前高度低的元素

在上面的例子中，左边第一个比 5 低的元素是 1（下标 1），右边第一个比 5 低的元素是 2（下标 4）

我们可以通过右边下标 - 左边下标 - 1 来求出高度为 5 能组成的最大长方形的宽，也就是 4 - 1 - 1 = 2

于是，面积就是 2 * 5 = 10

解决了如何计算所有高度的最大面积后，我们很自然的可以遍历所有高度，然后针对每一个高度遍历出第一个左右比当前低的下标求面积

但是为了进一步降低复杂度，我们需要再进一步思考，我们是否可以在一次遍历中同时求出左右下标？

答案是可以的，我们可以用一个单调栈来实现，这个栈是单调递增的，会按顺序保存所有比当前元素低的元素

我们用单调栈的视角来过一次上面的例子：

首先，我们需要给单调栈一个 “哨兵”（-1），这个哨兵的作用是让我们上面的 右边下标 - 左边下标 - 1 公式在 heights 左边界时也能持续生效

其次，我们需要遍历 heights，在遍历中比较当前 stack 栈顶元素与当前 heights[i] 的高度：

• 如果当前高度比栈顶高，直接把当前的下标入栈（选择下标是因为计算 width 只需要下标，而且高度可以通过下标获得）
• 如果当前高度比栈顶低（或者相等），我们需要把栈中比当前高度高的元素全部出栈

在元素出栈的时候，我们要顺势计算出栈高度能组成的最大长方形面积，怎么计算呢？

还是刚刚的思路，首先高度就是可以通过出栈的下标去 heights 中找到；其次宽度我们需要找到左右下标

而当前出栈元素的左下标就是它在栈中的上一个元素；右下标就是当前遍历元素

通过刚刚的思路遍历完所有元素后，我们还需要写另外一个循环把栈中剩下元素清空

或者，我们可以给 height push 一个非常低的高度，让它在最后一次循环中把栈清空，比如 -1

至此，我们就可以在一次循环中结束所有计算

Javascript

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function (heights) {
    // monotonous stack(increasing)
    const stack = [-1]
    // a little tricky, this can avoid another loop
    heights.push(-1)
    let res = 0

    for (let i = 0; i < heights.length; i++) {
        // 1. maintain the monotonous stack by pop every height smaller/equal than current height
        while (stack.length > 1 && heights[stack[stack.length - 1]] >= heights[i]) {
            const idx = stack.pop()
            // 2. calculate the area
            const height = heights[idx]
            const width = i - stack[stack.length - 1] - 1
            res = Math.max(res, height * width)

        }
        // 3. push current height's index to the stack
        stack.push(i)
    }

    return res
};