Leetcode 1139：最大的以 1 为边界的正方形（超详细的解法！！！）

大家好，欢迎来到IT知识分享网。

给你一个由若干 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

解题思路

首先我们不难想到暴力法，假设给定的grid长为c，高为r，我们从大到小遍历区间[0,min(r,c)]内的值k，我们以这个k作为正方形的宽度，然后遍历grid的每个点，分别以它作为正方形的左上角点。我们检查这个边长为k的正方形是不是合法，如果合法，那么此时就是最大的正方形，返回k2即可。

class Solution: def largest1BorderedSquare(self, grid: List[List[int]]) -> int: r, c = len(grid), len(grid[0]) def check(x1, y1, x2, y2): for x in range(x1, x2): if grid[x][y1] != 1 or grid[x][y2-1] != 1: return False for y in range(y1, y2): if grid[x1][y] != 1 or grid[x2-1][y