题目描述

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

示例

示例1:

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

示例2:

1
2
输入：matrix = []
输出：0

示例3:

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

示例4:

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

示例5:

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

提示

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

代码

暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public int maximalRectangle(char[][] matrix) {
        int rows = matrix.length;
        if (rows == 0) return 0;
        int cols = matrix[0].length;
        int [][]arr = new int[rows][cols+1];
        for (int i = 0; i < rows; ++i) {
            arr[i][0] = 0;
        }
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (matrix[i][j] == '1') arr[i][j+1] = arr[i][j]+1;
                else arr[i][j+1] = 0;
            }
        }
        int max = 0;
        int tmpx=-1, tmpy=-1;
        for (int i = 0; i < rows; ++i) {
            for (int j = 1; j < cols+1; ++j) {
                if (arr[i][j] != 0) {
                    int height = 2;
                    int mi = arr[i][j];
                    max = mi > max ? mi : max;
                    for (int tmp = i-1; tmp >= 0; --tmp) {
                        mi = Math.min(arr[tmp][j], mi);
                        int val = mi * height;
                        max = val > max ? val : max;
                        ++height;
                        if (max == 25) {
                            tmpx = i;
                            tmpy = j;
                        }
                    }
                }
            }
        }
        return max;
    }
}

单调栈+常数优化

与本博客文章 “柱状图中最大的矩形” 同理，有兴趣可以去阅读另外一篇博客。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public int maximalRectangle(char[][] matrix) {
        int rows = matrix.length;
        if (rows == 0) return 0;
        int cols = matrix[0].length;
        int [][]arr = new int[rows][cols+1];
        for (int i = 0; i < rows; ++i) {
            arr[i][0] = 0;
        }
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (matrix[i][j] == '1') arr[i][j+1] = arr[i][j]+1;
                else arr[i][j+1] = 0;
            }
        }
        int max = 0;
        for (int i = 1; i < cols+1; ++i) {
            int []left = new int[rows];
            int []right = new int[rows];
            for (int k = 0; k < rows; ++k) {
                right[k] = rows;	// 初始值为rows
            }
            Deque<Integer> stack = new LinkedList<Integer>();
            for (int j = 0; j < rows; ++j) {
                while (!stack.isEmpty() && arr[stack.peek()][i] >= arr[j][i]) {
                    right[stack.peek()] = j;	// 优化成一次遍历
                    stack.pop();
                }
                left[j] = (stack.isEmpty() ? -1 : stack.peek());
                stack.push(j);
            }
            for (int k = 0; k < rows; ++k) {
                int tmp = (right[k]-left[k]-1) * arr[k][i];
                max = tmp > max ? tmp : max;
            }
        }
        return max;
    }
}

题目来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximal-rectangle