题目描述

image-20221123200508883

思路分析

预处理数组

  • 由于只需要求边全为0的情况，所以可以用两个数组来分别存某个坐标连续0的长度

    • right: 表示从当前点开始，往右最长连续0的数量
    • down: 表示从当前点开始，往下最长连续0的数量

  • 有了这两个数组之后，之后只需要枚举可能的长度即可

  • 即通过固定左上角坐标来查看右上角坐标down数组的值rs和左下角坐标right数组的值ds

  • 需要特别注意边界情况的考虑

    • 比如rs和ds需要求一个小值（因为是正方形，多求无意义且可能越界），且遇到不满足的情况应该跳过，否则将错过

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      // case 1
      0 0 0
      0 1 0
      0 0 0
          
      // case 2
      0 0 0 0 0
      0 0 1 1 1
      0 1 1 1 0
      1 1 1 1 1

    • 坐标求法：在长度基础上减一（代码中rj和di）

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
class Solution {
public:
    vector<int> findSquare(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> right(m, vector<int>(n));
        for (int i = 0; i < m; i++) {
            right[i][n - 1] = matrix[i][n - 1] == 0 ? 1 : 0;
            for (int j = n - 2; j >= 0; j--) {
                right[i][j] = matrix[i][j] == 0 ? 1 + right[i][j + 1] : 0;
            }
        }
        vector<vector<int>> down(m, vector<int>(n));
        for (int j = 0; j < n; j++) {
            down[m - 1][j] = matrix[m - 1][j] == 0 ? 1 : 0;
            for (int i = m - 2; i >= 0; i--) {
                down[i][j] = matrix[i][j] == 0 ? 1 + down[i + 1][j] : 0;
            }
        }
        vector<int> res;
        // 固定左上角，尝试不同长度的右上和左下是否达标
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) continue;
                int r = right[i][j];
                int d = down[i][j];
                int siz = min(r, d);
                for (int s = 1; s <= siz; s++) {
                    int ri = i, rj = j + s - 1;
                    int rs = down[ri][rj];
                    int di = i + s - 1, dj = j;
                    int ds = right[di][dj];
                    // break 换 continue
                    // 跳过此次比较，长度更长的还是有可能的
                    if (rs < s || ds < s) continue;
                    if (res.empty() || res[2] < s) {
                        res = {i, j, s};
                    }
                }
            }
        }

        return res;
    }
};

image-20221123201533286