题目大意：
最大的以 1 为边界的正方形
给你一个由若干 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
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1139
解题思路分析：
这道题是要求出四周由1能够组成的最大正方形面积。注意只是边为1即可，中间的部分可以是1也可以是0。最简单的思路就是暴力算法，以每一个点为顶点，向右侧和下侧画正方形，正方形的边长由1到左侧或者下侧的边界为止逐个循环，如果正方形四边上的数字和与边长相同，则他是符合题目要求的一个候选解，直到循环结束即可遍历出最优答案。
这里需要使用到三层循环，横坐标纵坐标各需要一层，循环正方形边长需要一层，这样运行时间上很可能会超时。因此我们需要做一些优化和剪枝。首先以0为顶点的正方形肯定是不合法的，直接略过，另外，在计算边长时，我们可以使用preSum前缀和的方式提前做好计算，方便快速的得到任意两点间的距离，减少重复计算。
看下完整代码：
public int largest1BorderedSquare(int[][] grid) {
int[][] memo_r = new int[grid.length][grid[0].length]; // 横向前缀和
int[][] memo_c = new int[grid.length][grid[0].length]; // 纵向前缀和
for(int r=0;r<grid.length;r++){
for(int c=0;c<grid[0].length;c++){
if(c==0){
memo_c[r][c] = grid[r][c];
}else{
memo_c[r][c] = memo_c[r][c-1] + grid[r][c];
}
if(r==0){
memo_r[r][c] = grid[r][c];
}else{
memo_r[r][c] = memo_r[r-1][c] + grid[r][c];
}
}
}
int res = 0; // 结果
for(int r=0;r<grid.length;r++){ // 循环纵坐标
for(int c=0;c<grid[0].length;c++){ // 循环横坐标
int value = grid[r][c]; // 当前点
if(value==0){ // 顶点为0直接略过
continue;
}
// 防止正方形越界，计算当前点到底边和右边的最小值作为正方形最大边长。
int maxLength = Math.min(grid.length - r, grid[0].length - c);
for(int i = 0; i<maxLength;i++){
int top = memo_r[r+i][c] - memo_r[r][c] + value;
int bottom = memo_r[r+i][c+i] - memo_r[r][c+i] + value;
int left = memo_c[r][c+i] - memo_c[r][c] + value;
int right = memo_c[r+i][c+i] - memo_c[r+i][c] + value;
// 四条边之和是否等于周长
if(top+bottom+left+right == (i+1) * 4){
res = Math.max(res, (i+1)*(i+1)); // 更新结果
}
}
}
}
return res;
}本解法用时16ms。效率不高但可以通过。二刷时再考虑更优解法。
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/1139-largest-1-bordered-square解题思路分析/