leetcode 1139
问题 Given a 2D grid
of 0
s and 1
s, return the number of elements in the largest square subgrid that has all 1
s 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: 声明两个矩阵 rowSums
和 colSums
用来分别保存每一行的前缀和和每一列的前缀和。然后遍历每一个 (i, j) 求出以它为右下顶点符合要求的最大正方形长度是多少。依次遍历k,则有左上角的坐标 (x0, y0) = (i-k+1, j-k+1);
于是我们利用 rowSums
和 colSums
就可以求出四个边长分别是多少,判断其是否全部等于k,就可以更新答案。时间复杂度 $O(n^3)$
思路2: 求出两个辅助矩阵,分别表示每一行到 (i, j) 连续的1的个数,以及每一列到 (i, j) 连续的1的个数。
于是,我们就可以从右下方开始向上进行遍历,判断每一个以 (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 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; } };