[LeetCode] 85. Maximal Rectangle

Given a rows x cols binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

Example 1:

Input: matrix = [
[“1”,”0”,”1”,”0”,”0”],
[“1”,”0”,”1”,”1”,”1”],
[“1”,”1”,”1”,”1”,”1”],
[“1”,”0”,”0”,”1”,”0”]
]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

Example 2:
Input: matrix = [[“0”]]
Output: 0

Example 3:
Input: matrix = [[“1”]]
Output: 1

Constraints:
rows == matrix.length
cols == matrix[i].length
1 <= row, cols <= 200
matrix[i][j] is ‘0’ or ‘1’.

最大矩形。

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

思路

题意是给一个二维矩阵，求二维矩阵里面由1组成的最大矩形的面积是什么。这个题有DP和单调栈两种做法，我这里给出单调栈的解法。思路跟84题类似，你可以把每一行想象成84题的bars，跑一下第一个例子，比如我们从最后一行往上遍历，最后一行是
[1, 0, 0, 1, 0]

按照84题的思路，能组成的最大的矩形面积是 1。
接着把倒数第二行的数字叠加进来，叠加的思路是，若下一行相同位置上为0，则当前位置是1；若下一行相同位置上不为0，则当前位置 + 1。

[1, 1, 1, 1, 1]
[1, 0, 0, 1, 0]

得到
[2, 1, 1, 2, 1]

从而得到最大矩形面积是2。以此类推可以得到这个4*5的矩阵里面最大的矩形的面积。

复杂度

时间O(mn^2)
空间O(n)

代码

Java实现

class Solution {
    public int maximalRectangle(char[][] matrix) {
        // corner case
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        // normal case
        int row = matrix.length;
        int col = matrix[0].length;
        int[] heights = new int[col];
        int max = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == '1') {
                    heights[j]++;
                } else {
                    heights[j] = 0;
                }
            }
            int area = helper(heights);
            max = Math.max(max, area);
        }
        return max;
    }

    private int helper(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        for (int i = 0; i <= heights.length; i++) {
            int cur = i == heights.length ? 0 : heights[i];
            while (!stack.isEmpty() && cur < heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int start = stack.isEmpty() ? -1 : stack.peek();
                int area = height * (i - start - 1);
                res = Math.max(res, area);
            }
            stack.push(i);
        }
        return res;
    }
}

JavaScript实现

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

    // normal case
    let res = 0;
    let row = matrix.length;
    let col = matrix[0].length;
    let heights = new Array(col).fill(0);
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if (matrix[i][j] == '1') {
                heights[j]++;
            } else {
                heights[j] = 0;
            }
        }
        let area = helper(heights);
        res = Math.max(res, area);
    }
    return res;
};

var helper = function(heights) {
    // corner case
    if (heights == null || heights.length == 0) {
        return 0;
    }

    // normal case
    let stack = [];
    let res = 0;
    for (let i = 0; i <= heights.length; i++) {
        let h = i == heights.length ? 0 : heights[i];
        while (stack.length && h < heights[stack[stack.length - 1]]) {
            let height = heights[stack.pop()];
            let start = !stack.length ? -1 : stack[stack.length - 1];
            let area = height * (i - start - 1);
            res = Math.max(res, area);
        }
        stack.push(i);
    }
    return res;
};

相关题目

84. Largest Rectangle in Histogram
85. Maximal Rectangle
221. Maximal Square
1277. Count Square Submatrices with All Ones
1727. Largest Submatrix With Rearrangements