leetcode 1139

问题

Given a 2D grid of 0s and 1s, return the number of elements in the largest square subgrid that has all 1s on its border, or 0 if such a subgrid doesn’t exist in the grid.

Example 1:

1
2
Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: 9

Example 2:

1
2
Input: grid = [[1,1,0,0]]
Output: 1

Constraints:

  • 1 <= grid.length <= 100
  • 1 <= grid[0].length <= 100
  • grid[i][j] is 0 or 1

分析

思路1: 声明两个矩阵 rowSumscolSums 用来分别保存每一行的前缀和和每一列的前缀和。然后遍历每一个 (i, j) 求出以它为右下顶点符合要求的最大正方形长度是多少。依次遍历k,则有左上角的坐标 (x0, y0) = (i-k+1, j-k+1); 于是我们利用 rowSumscolSums 就可以求出四个边长分别是多少,判断其是否全部等于k,就可以更新答案。时间复杂度 $O(n^3)$

思路2: 求出两个辅助矩阵,分别表示每一行到 (i, j) 连续的1的个数,以及每一列到 (i, j) 连续的1的个数。

image

于是,我们就可以从右下方开始向上进行遍历,判断每一个以 (i, j) 作为右下角的符合要求的最大正方形长度是多少。这个方法剪枝效果比较好。goelrishabh5-concise-with-algorithm-and-image)

代码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
// O(n^2)
int largest1BorderedSquare(vector<vector<int>>& grid) {
int ans = 0;
int m = grid.size();
int n = grid[0].size();

vector<vector<int>> rowSums(m, vector<int>(n, 0));
vector<vector<int>> colSums(m, vector<int>(n, 0));

for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
colSums[i][j] = grid[i][j] + (i==0? 0: colSums[i-1][j]);
rowSums[i][j] = grid[i][j] + (j==0? 0: rowSums[i][j-1]);
}
}

for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = ans+1; i-k+1 >= 0 && j-k+1 >=0; ++k) {
int x0 = i-k+1;
int y0 = j-k+1;

int row0 = rowSums[x0][j] - (y0 > 0? rowSums[x0][y0-1]: 0);
int row1 = rowSums[i][j] - (y0 > 0? rowSums[i][y0-1]: 0);

int col0 = colSums[i][y0] - (x0 > 0? colSums[x0-1][y0]: 0);
int col1 = colSums[i][j] - (x0 > 0? colSums[x0-1][j]: 0);

if (row0 == k && row1 == k && col0 == k && col1 == k) {
ans = k;
}
}
}
}
return ans*ans;

}

代码2

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
class Solution {
public:
int largest1BorderedSquare(vector<vector<int>>& grid) {
int ans = 0;
int m = grid.size();
int n = grid[0].size();

vector<vector<int>> ver(m, vector<int>(n, 0));
vector<vector<int>> hor(m, vector<int>(n, 0));

for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
ver[i][j] = 1 + (i == 0? 0: ver[i-1][j]);
hor[i][j] = 1 + (j == 0? 0: hor[i][j-1]);
}
}
}

for (int i = m-1; i >= 0; --i) {
for (int j = n-1; j >= 0; --j) {
int k = min(ver[i][j], hor[i][j]);
while (k > ans) {
if (ver[i][j-k+1] >= k && hor[i-k+1][j] >= k)
ans = k;
--k;
}
}
}
return ans*ans;

}
};