难度: Medium
给你一个由若干 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 <= 1001 <= grid[0].length <= 100grid[i][j] 为 0 或 1运行时间: 43 ms
内存: 16.5 MB
class Solution:
def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
row = [[0] * n for _ in range(m)]
col = [[0] * n for _ in range(m)]
max_l = 0
# 状态转移
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
row[i][j] = row[i][j-1] + 1 if j else 1
col[i][j] = col[i-1][j] + 1 if i else 1
cur_max = min(row[i][j], col[i][j])
while cur_max >= max_l:
x = i - cur_max + 1
y = j - cur_max + 1
if row[x][j] >= cur_max and col[i][y] >= cur_max:
max_l = cur_max
break
cur_max -= 1
return max_l ** 2
该题解采用动态规划的思想。首先，创建两个二维数组row和col，其中row[i][j]表示在grid[i][j]处，从该点向左连续的1的数量；col[i][j]表示在grid[i][j]处，从该点向上连续的1的数量。然后，遍历整个网格，对于每一个点(grid[i][j] == 1)，我们检查以该点为右下角的正方形的最大边长。这里的最大边长取决于从该点向左和向上连续的1的数量（即row[i][j]和col[i][j]的较小值）。对于可能的每个边长，我们检查相应的左边界和上边界是否满足条件（即是否包含足够数量的连续的1）。如果满足条件，我们更新最大正方形的边长。最后，返回最大边长的平方，即最大正方形中的元素数量。
时间复杂度: O(mn * min(m, n))
空间复杂度: O(mn)
class Solution:
def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
row = [[0] * n for _ in range(m)]
col = [[0] * n for _ in range(m)]
max_l = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
row[i][j] = row[i][j-1] + 1 if j else 1
col[i][j] = col[i-1][j] + 1 if i else 1
cur_max = min(row[i][j], col[i][j])
while cur_max >= max_l:
x = i - cur_max + 1
y = j - cur_max + 1
if row[x][j] >= cur_max and col[i][y] >= cur_max:
max_l = cur_max
break
cur_max -= 1
return max_l ** 2
在这个算法中，我们的目标是找到以某点为右下角的最大正方形。因此，每个格子只需要知道从它向左以及向上能延伸出多少连续的1。这是因为正方形的验证从右下角开始，首先检查左侧和上侧的连续性。向右和向下的连续性在这个场景中不直接贡献于形成以当前点为右下角的正方形边界。
动态规划的关键在于使用先前计算的状态（连续的1的数量）来帮助快速计算后续状态，避免重复计算。对于每个点grid[i][j]，我们根据它的左边点（grid[i][j-1]）和上边点（grid[i-1][j]）的状态来更新当前点的row和col数组。如果grid[i][j]是1，那么row[i][j]就是row[i][j-1] + 1，col[i][j]就是col[i-1][j] + 1。这种方法使得我们能够在处理每个点时快速得出从该点向左和向上的连续1的数量。
检查每个可能的边长时，我们从当前点能形成的最大可能边长（即row[i][j]和col[i][j]中较小的那个）开始向下逐步检查，直到边长小于已知的最大边长max_l。这样做是因为，如果当前正在检查的边长已经小于我们之前找到的最大边长max_l，那么即使这个边长是有效的，它也不会帮助我们得到一个更大的正方形。因此，这个停止条件帮助我们省去了不必要的计算，并尽快地跳出循环。
因为row[x][j]代表从点(x, j)开始向左的连续1的数量，而col[i][y]表示从点(i, y)开始向上的连续1的数量。在检查一个潜在的边长是否可以形成正方形时，我们需要确保左边界和上边界的长度至少与当前考虑的边长相等。检查row[x][j]可以保证从右下角的正方形的左上角到左下角的水平线段是连续的1，检查col[i][y]可以保证从右下角的正方形的左上角到右上角的垂直线段是连续的1。这两个检查确保了正方形的左边界和上边界是完整的。