85. 最大矩形

[webVueBlog]

85. 最大矩形

Description

Difficulty: 困难

Related Topics: 栈, 数组, 动态规划, 矩阵, 单调栈

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。

示例 2：

输入：matrix = []
输出：0

示例 3：

输入：matrix = [["0"]]
输出：0

示例 4：

输入：matrix = [["1"]]
输出：1

示例 5：

输入：matrix = [["0","0"]]
输出：0

提示：

• rows == matrix.length
• cols == matrix[0].length
• 1 <= row, cols <= 200
• matrix[i][j] 为 '0' 或 '1'

Solution

Language: JavaScript

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalRectangle = function(matrix) {
    if (matrix.length === 0) return 0

    let res = 0
    let heights = new Array(matrix[0].length).fill(0) // 初始化heights数组
    for (let row = 0; row < matrix.length; row++) {
        for (let col = 0; col < matrix[0].length; col++) {
            if (matrix[row][col] === '1') heights[col] += 1
            else heights[col] = 0
        } // 求出每一层的 heights[] 然后传给 largestRectangleArea 函数
        res = Math.max(res, largestRectangleArea(heights)) // 更新一下最大矩形面积
    }
    return res
};

const largestRectangleArea = (heights) => {
    let maxArea = 0
    const stack = [] // 单调递增栈 注意栈存的是下标
    heights = [0, ...heights, 0] // 在 heights 数组前后增加两个哨兵 用来清零单调递增栈里的元素
    for (let i = 0; i < heights.length; i++) {
        // 当前元素对应的高度小于栈顶元素对应的高度时
        while (heights[i] < heights[stack[stack.length - 1]]) {
            const stackTopIndex = stack.pop() // 出栈
            maxArea = Math.max(
                maxArea,
                heights[stackTopIndex] * (i - stack[stack.length - 1] - 1) // 高乘宽
            )
        }
        stack.push(i) // 当前下标加入栈
    }
    return maxArea
}