题目

221. 最大正方形

在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。

image.png

1
2
3
4
m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 '0' 或 '1'

思路1-前缀和

思路1说明

面试的时候遇到了这道题，当时只想得出来遍历的办法，后来面试官提示了一下想出来了另外一个思路，不过没时间写了。

思路是这样的，开另外一个和题目所给矩阵一样的二维数组vector<vector<pair<int, int>>>，用于存放每一位的往前1的个数和往上1的个数（不包括该数自己）。

以题目给的矩阵为例

1
2
3
4
5
6
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]

可以得到下面的前缀和矩阵，每一位的左侧代表该位置行之前的1的个数，右侧代表该位置列往上1的个数（不包括该数自己）

1
2
3
4
{0,0} {1,0} {1,0} {2,0} {2,0}
{0,1} {1,0} {1,1} {2,0} {3,0}
{0,2} {1,0} {2,2} {3,1} {4,1}
{0,3} {0,1} {1,3} {1,2} {2,2}

此时要确定一个正方形，以示例图中下标(1,2)到(2,3)的这个2x2的正方形为例，我们只需要判断正方形对角线上的数的前缀和是否符合条件即可。一个符合条件的正方形，假设下标从(0,0)开始，它的对角线上的前缀和应该是这样的，分别代表该位置之前和之上1的数量。

(0,0)
(1,1)
(2,2)
……

但我们需要找的下标(1,2)到(2,3)的正方形并不是从(0,0)开始的，所以还需要对这个前缀和矩阵中的值进行一定处理来得到结果。过程如下

  • 下标(1,2)是1，开始处理（判断从这个坐标开始往左下角的最大正方形）；
  • 正方形边长初始化为1（因为起始下标位置为1，就是一个1x1的正方形）；
  • 判断(1+1,2+1)下标处的值是否为1；为1继续判断前缀和，值是{3,1}；
  • 这里前缀和的3代表这一行前面还有3个1，1代表这一列上面还有1个1；
  • 行需要和下标(2,2)处的前缀和{2.2}第一位相减；列需要和下标(1,2)处的前缀和{2,0}第二位相减。即{3-2,1-0}，最终得到的结果是1,1，符合正方形对角线上的条件，边长加一为2。
  • 继续判断(2+1,3+1)下标处的值是否为1，此时发现已不为1，停止匹配；
  • 得到最大正方形边长2，面积为4；

如果是下面这样的矩阵（相比上面的矩阵只修改了左下角的两个0为1）

1
2
3
4
5
6
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","1","1","1"]
]

对应前缀和矩阵如下

1
2
3
4
{0,0} {1,0} {1,0} {2,0} {2,0}
{0,1} {1,0} {1,1} {2,0} {3,0}
{0,2} {1,0} {2,2} {3,1} {4,1}
{0,3} {0,1} {1,3} {2,2} {3,2}

此时(2+1,3+1)下标处的值为1，继续判断前缀和{3,2}，这时候已经是一个3x3的正方形了，这个对角线的值应为{2,2}才符合条件。所以需要计算当前前缀和与行的前2个和列的前2个的差值：

  • 行需要和下标(3,2)处的前缀和{1,3}第一位相减；
  • 列需要和下标(1,4)处的前缀和{3,0}第二位相减；
  • 即{3-1,2-0}，最终能得到{2,2}，符合正方形条件；
  • 边长加一为3，最大正方形面积为9。

以此类推，直到遍历的下标越界为止，即完成了对矩阵中一个位置的正方形查找。

这里涉及到两次叠加循环和一个扩张循环，时间复杂度可以认为是O(N^3)或O(M^3)；

思路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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.size() == 0) {
            return 0;
        }
        // 用于记录前缀和，下标代表这个数的行之前以及列以上的1的个数（不包括该数本身）
        int n = matrix.size(), m = matrix[0].size();
        vector<vector<pair<int, int>>> oneCount(
            n, vector<pair<int, int>>(m, {0, 0}));
        oneCount[0][0] = {0, 0};
        // O(M*N)
        for (int i = 0; i < matrix.size(); i++) {
            int count = 0; // 每一行的1计数器
            for (int j = 0; j < matrix[i].size(); j++) {
                // 第i行，j之前的1的个数（不包括当前值）
                oneCount[i][j].first = count; // 先赋值，因为不包括自己
                // 第i行，第j列往上1的个数（不包括当前值）
                if (i == 0) {
                    oneCount[i][j].second = 0;
                } else {
                    // 直接拿上一层的值为初值，再判断上一层是否为1
                    oneCount[i][j].second = oneCount[i - 1][j].second;
                    if (matrix[i - 1][j] == '1') {
                        oneCount[i][j].second++;
                    }
                }

                // 每一行的1的个数加一
                if (matrix[i][j] == '1') {
                    count++;
                }
            }
        }

        // 此时可以得到一个矩阵，这样判断是否为正方形只需要判断对角线的数
        int maxSquare = 0;
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[i].size(); j++) {
                // 一个位置等于1的时候就是一个1x1的正方形了
                if (matrix[i][j] == '1') {
                    // 从2x2的位置开始判断
                    int a = i + 1, b = j + 1;
                    int length = 1;      // 当前正方形边长
                    int lengthCheck = 1; // 正方形条件判断计数器
                    // 出现越界的时候停止扩张
                    while (a < matrix.size() && b < matrix[i].size()) {
	                    // 这里不能用引用，避免修改数组里面的原始值
                        pair<int, int> p = oneCount[a][b];
                        // 注意这里扩张的时候需要用lengthCheck来相减计算，而不是简单的减一
                        // 因为边长每扩大一次需要减的位置也会扩大一次
                        p.first -=
                            oneCount[a][b - lengthCheck].first; // 行的前一个
                        p.second -=
                            oneCount[a - lengthCheck][b].second; // 列的上一个

                        // 符合正方形要求
                        if (matrix[a][b] == '1' && (p.first == lengthCheck &&
                                                    p.second == lengthCheck)) {
                            lengthCheck++;
                            length++;
                        } else {
                            break; // 不符合就跳出
                        }
                        a++;
                        b++;
                    }
                    // 计算面积，更新最大值
                    int square = length * length;
                    maxSquare = square > maxSquare ? square : maxSquare;
                }
            }
        }
        return maxSquare;
    }
};

思路2-动态递归

因为我还没有开始学动归的算法，只学一道题其他的还是不会，不如留着到时候一起回顾。