day6 最大正方形

不懂一点人生。

读题

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
输入是一个二维数组/矩阵 vector<vector<char>>。
提示：

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

这个 m 即是矩阵的列数，n 是行数，有范围限制；矩阵内部元素固定为 0 或 1。

思路

第一思路

第一反应是针对每一个为 1 的方块，向下向右搜索其他为 1 的方块，时间复杂度应该是 O(n^2) 甚至 O(n^4)？虽说用时可能会比较长，但是长宽固定为 300，先试试再说。
需要先有一个方法 fun 判断从该点出发，右下多大的为全为 1 的正方形：

  1. 接受参数边长 l，指针 root，返回 true 和 false。
  2. 如果 l 大于等于 3，调用 fun 自己，判断 l-1 的正方形是否存在
    1. 若存在，调用 fun_edge 判断边界是否全为 1。
      1. 若是，返回 true。
      2. 若否，返回 false。
    2. 若不存在，返回 false。

使用一个方法 fun_edge 判断边界的是否存在：

  1. 接受参数边长 l，指针 root，返回 true 和 false。
  2. 直接判断
    1. 如果遇到 0，返回 false。
  3. 返回 true。

总体的过程是：

  1. 从左上角[0][0]开始
  2. 先右后下遍历，当前位置为[i][j]
    1. 如果当前位置为 1，调用方法 fun_edge，判断边长 2的正方形是否存在
    2. 继续调用 fun_edge，直到边长为 max{30-i, 30-j}，或者 fun_edge 返回 false。
  3. 继续

于是有代码：

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
class Solution {
public:
    bool fun_edge(int l, int i, int j, vector<vector<char>>& matrix){
        for (int x=i; x<i+l; x++) {
            if (matrix[x][j+l-1] == '0') return false;
        }
        for (int y=j; y<j+l; y++) {
            if (matrix[i+l-1][y] == '0') return false;
        }
        return true;
    }
    int maximalSquare(vector<vector<char>>& matrix) {
        int m=matrix.size();
        int n=matrix[0].size();
        int max_l = 0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]=='1'){
                    if(max_l==0) max_l=1;
                    for(int l=1;l<=min(m-i,n-j);l++){
                        if(fun_edge(l,i,j,matrix)){
                            if(l>max_l) max_l=l;
                        } else break;
                    }
                }
            }
        }
        return max_l*max_l;
    }
};

能跑，但在部分测试用例里不出所料地超时了。

改变思路

或许逐个判断小正方形还是太大了，可以先判断大的（因为边界是固定的有限长度），然后逐步收紧，判断小的。
又或许可以记录每个点位可以构成的最大的正方形的边长，这样无需重复判断。使用一个同为 m×n 的矩阵来记录。对于一个点位，如果它在 matrix 里是 1，那么它可以作为成员参与到构建更大的正方形；如果其右边的一个点位、下面的一个点位、右下的一个点位也是 1，那么可以构成一个 2×2 的正方形。这是常规思路。如果其右边的一个点位、下面的一个点位、右下的一个点位都是 2×2 正方形的左上端点，那么加上这个点位本身，就可以构成一个 3×3 的正方形。以此类推。
啊啊，或许改成右下端点更合适？这样正方形可以从左上向右下扩大。，而不是向左上
于是有过程：

  1. 初始化，得到 m，n，全为 0 的空 len_matrix 矩阵
  2. 循环遍历所有的点位
    1. 如果当前点位为 1
      1. 如果是 matrix 的左边界上边界顶点
        1. 那么只能是边长为 1 的正方形，记录到 len_matrix 矩阵中。
      2. 如果是其他点，获取其左边一个、上面一个、左上一个点能构成正方形的最大边长（len_matrix 对应点位的值）
      3. 该点位的 len_matrix 是三者最小值加一。
    2. 赋值 max_len
    3. 继续
  3. 继续
  4. 返回 max_len×max_len

有代码：

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
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m=matrix.size();
        int n=matrix[0].size();
        vector<vector<int>> len_matrix(m, vector<int>(n, 0)); // 这个是全0二维数组
        int max_len=0;
        
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (matrix[i][j]=='1') {
                    if (i==0 || j==0) {
                        len_matrix[i][j]=1;  // 第一行或第一列上的'1'只能形成1x1的正方形
                    } else {
                        len_matrix[i][j]=min({len_matrix[i-1][j],
                                              len_matrix[i][j-1],
                                              len_matrix[i-1][j-1]}) + 1;
                    }
                    max_len=max(max_len, len_matrix[i][j]);
                }
            }
        }
        return max_len * max_len;
    }
};

结果

用时 9 ms，内存 30.54 MB。时间中等（不过起码过了），内存吃得多（我还以为已经很少了）。

官方题解

方法一：暴力法

题解言：
由于正方形的面积等于边长的平方，因此要找到最大正方形的面积，首先需要找到最大正方形的边长，然后计算最大边长的平方即可。
暴力法是最简单直观的做法，具体做法如下：

  • 遍历矩阵中的每个元素，每次遇到 1，则将该元素作为正方形的左上角；
  • 确定正方形的左上角后，根据左上角所在的行和列计算可能的最大正方形的边长（正方形的范围不能超出矩阵的行数和列数），在该边长范围内寻找只包含 1 的最大正方形；
  • 每次在下方新增一行以及在右方新增一列，判断新增的行和列是否满足所有元素都是 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
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) {
            return 0;
        }
        int maxSide = 0;
        int rows = matrix.size(), columns = matrix[0].size();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    // 遇到一个 1 作为正方形的左上角
                    maxSide = max(maxSide, 1);
                    // 计算可能的最大正方形边长
                    int currentMaxSide = min(rows - i, columns - j);
                    for (int k = 1; k < currentMaxSide; k++) {
                        // 判断新增的一行一列是否均为 1
                        bool flag = true;
                        if (matrix[i + k][j + k] == '0') {
                            break;
                        }
                        for (int m = 0; m < k; m++) {
                            if (matrix[i + k][j + m] == '0' || matrix[i + m][j + k] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        if (flag) {
                            maxSide = max(maxSide, k + 1);
                        } else {
                            break;
                        }
                    }
                }
            }
        }
        int maxSquare = maxSide * maxSide;
        return maxSquare;
    }
};

看了之后感觉还不如我的……拿去提交试了一下，果不其然也会超时。
复杂度是 O(m*n*min(m,n)^2)。

方法二：动态规划

类似我的，但是更严谨；使用了状态转移方程和严谨的逻辑推导。

收获

  1. 暴力是可取的，但不一定是能过提交的。
  2. 动态规划……是什么？
  3. 可以使用类似马尔可夫链的思想，保存所谓状态，并令状态作为影响决策的因素。这一点感觉类似前天单调栈？但又不是很一样。

这太酷了。

day6 最大正方形
http://blog.wspdwzh.space/2025/10/23/day6-最大正方形/
作者
peter？
发布于
2025年10月23日
许可协议