题目

84. 柱状图中最大的矩形

困难

相关标签

相关企业

给定 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

题解

/**
 * 暴力1
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function (heights) {
    let maxArea = 0;
    for (let i = 0; i < heights.length - 1; i++) {
        for (let j = i + 1; j < heights.length; j++) {
            const minHeight = Math.min(...heights.slice(i, j+1))
            maxArea = Math.max(maxArea, (j - i + 1) * minHeight)
        }
    }
    return maxArea
};
/**
 * 暴力2  找边界
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function (heights) {
    let maxArea = 0;
    for (let i = 0; i < heights.length - 1; i++) {
        const curHeight = heights[i]
        let leftBound = i;
        let rightBound = i;
        while(leftBound-1 >= 0 && heights[leftBound-1] >= curHeight ) {
            leftBound --
        }
        while(rightBound+1 <= heights.length && heights[rightBound+1] >= curHeight ) {
            rightBound ++
        }
        maxArea = Math.max(maxArea, (rightBound - leftBound + 1) * curHeight)
    }
    return maxArea
};
/**
 * 栈方法
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function (heights) {
    let maxArea = 0;
    const stackArr = [];
    heights = [0, ...heights, 0]
    for (let i = 0; i < heights.length; i++) {
        while (stackArr.length && heights[stackArr[stackArr.length - 1]] > heights[i]) {
            const stackPopIndex = stackArr.pop() // 栈顶元素出栈，并保存栈顶bar的索引
            maxArea = Math.max(maxArea, heights[stackPopIndex] * (i - stackArr[stackArr.length - 1] - 1))
        }
        stackArr.push(i)
    }
    return maxArea
};