LeetCode_前缀和_中等_1139.最大的以 1 为边界的正方形

爱被打了一巴掌 2023-10-08 17:44 64阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 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

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/largest-1-bordered-square

## 2.思路 ##

（1）前缀和  
思路参考该 [LeetCode 用户题解][LeetCode]。

![在这里插入图片描述][8a0db009471243c8883e088f258d60a0.png]

## 3.代码实现（Java） ##

//思路1————前缀和
    class Solution {
        
        public int largest1BorderedSquare(int[][] grid) {
        
            int m = grid.length;
            int n = grid[0].length;
            // rowPreSum[i][j] 表示第 i 行中前 j 个元素之和
            int[][] rowPreSum = new int[m][n + 1];
            // colPreSum[i][j] 表示第 i 列中前 j 个元素之和
            int[][] colPreSum = new int[n][m + 1];
            //初始化 rowPreSum 和 colPreSum
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    rowPreSum[i][j + 1] = rowPreSum[i][j] + grid[i][j];
                    colPreSum[j][i + 1] = colPreSum[j][i] + grid[i][j];
                }
            }
            //从大到小枚举边长为 d 的正方形
            for (int d = Math.min(m, n); d > 0; d--) {
        
                //枚举边长为 d 的正房形的左上角坐标 (i, j)
                for (int i = 0; i <= m - d; i++) {
        
                    for (int j = 0; j <= n - d; j++) {
        
                        //判断正方形的 4 条边是否均由 1 组成
                        if (rowPreSum[i][j + d] - rowPreSum[i][j] == d &&    //上边
                            colPreSum[j][i + d] - colPreSum[j][i] == d &&    //左边
                            rowPreSum[i + d - 1][j + d] - rowPreSum[i + d - 1][j] == d &&   //下边
                            colPreSum[j + d - 1][i + d] - colPreSum[j + d - 1][i] == d) {
           //右边
                            return d * d;
                        }
                    }
                }
            }
            //不存在最大的以 1 为边界的正方形
            return 0;
        }
    }

[LeetCode]: https://leetcode.cn/problems/largest-1-bordered-square/solution/tu-jie-qian-zhui-he-qing-song-acpythonja-5mnn/
[8a0db009471243c8883e088f258d60a0.png]: https://img-blog.csdnimg.cn/8a0db009471243c8883e088f258d60a0.png