【Leetcode】最大的以1为边界的正方形
题目链接:1139. 最大的以 1 为边界的正方形 - 力扣(Leetcode)
给你一个由若干 0
和 1
组成的二维网格 grid
,请你找出边界全部由 1
组成的最大 正方形 子网格,并返回该子网格中的元素数量。如果不存在,则返回 0
。
示例 1:
输入:grid = [[1,1,1],[1,0,1],[1,1,1]]
输出:9
示例 2:
输入:grid = [[1,1,0,0]]
输出:1
提示:
1 <= grid.length <= 100
1 <= grid[0].length <= 100
grid[i][j]
为0
或1
题解
这个题我最开始想的是用搜索来写,但是实际上发现用搜索太复杂了,可以采用DP的方式
我们用两个数组:left和up,分别记录以(i,j)
点起始,向左有多少连续的1以及向上有多少连续的一,这样就记录了这个方框的右边和下边的最大可能长度。通过这种方式,我们也可以知道出方框的上边和左边的最大长度: left[i - border + 1]
,right[j - border + 1]
,其中 border 是任意可能边长的长度。为了能组成一个正方形,我们需要四条边长度相等,即:取四条边最短的边作为正方形的边长即可。
ACCode
class Solution {
public:
int largest1BorderedSquare(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
// left[i][j] 以 i, j 为起点,向左最多有多少个 1
vector<vector<int>> left(m+1, vector<int>(n+1));
// up[i][j] 以 i,j为起点,向上最多有多少个1
vector<vector<int>> up(m+1, vector<int>(n+1));
int maxBorder = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; 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 border = min(left[i][j], up[i][j]);
while (left[i - border + 1][j] < border ||
up[i][j - border + 1] < border) {
border--;
}
maxBorder = max(maxBorder, border);
}
}
}
return maxBorder * maxBorder;
}
};
作者:NorthCity1984
出处:https://grimoire.cn/acm/largest-1-bordered-square.html
版权:本文《【Leetcode】最大的以1为边界的正方形》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任
出处:https://grimoire.cn/acm/largest-1-bordered-square.html
版权:本文《【Leetcode】最大的以1为边界的正方形》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任