[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) {
		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) {
		Deque<Integer> stack = new ArrayDeque<>();
		int n = heights.length;
		int res = 0;
		for (int i = 0; i <= n; i++) {
			int h = i == n ? 0 : heights[i];
			while (!stack.isEmpty() && h < heights[stack.peekLast()]) {
				int height = heights[stack.pollLast()];
				int start = stack.isEmpty() ? -1 : stack.peekLast();
				int area = height * (i - start - 1);
				res = Math.max(res, area);
			}
			stack.offerLast(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