题目简介：
给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。
示例 1：
1
2
| 输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
输出：9
|
示例 2：
1
2
| 输入：grid = [[1,1,0,0]]
输出：1
|
提示：
1 <= grid.length <= 1001 <= grid[0].length <= 100grid[i][j] 为 0 或 1
思路：
我们用left[x][y]来代表以(x, y)为起点**往左连续1的个数，up[x][y]为以(x, y)为起点往上**连续1的个数。
所以正方形边长可能的最大值为now_len = min(left[x][y], up[x][y])。(必定小于等于这两条边的边长)
我们假设(x, y)为正方形的右下角，那么剩余两条边的条件为left[i - now_len + 1][j] >= now_len && up[i][j - now_len + 1] >= now_len。
如果不满足，则不断缩小now_len，枚举即可。
最后得到的Maxlen便是正方形的最大边长。
代码如下：
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:
int largest1BorderedSquare(vector<vector<int>>& grid) {
vector<vector<int>> left(grid.size() + 1, vector<int>(grid[0].size() + 1));
vector<vector<int>> up(grid.size() + 1, vector<int>(grid[0].size() + 1));
int Maxlen = 0;
for(int i = 1; i <= grid.size(); i++){
for(int j = 1; j <= grid[i - 1].size(); j++){
if(grid[i - 1][j - 1] == 1){
left[i][j] = left[i][j - 1] + 1;
up[i][j] = up[i - 1][j] + 1;
int now_len = min(left[i][j], up[i][j]);
while(left[i - now_len + 1][j] < now_len || up[i][j - now_len + 1] < now_len)
now_len--;
Maxlen = max(Maxlen, now_len);
}
}
}
return Maxlen * Maxlen;
}
};
|
