本文共 3160 字，大约阅读时间需要 10 分钟。

给你一个由若干 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的正方形是不是合法，如果合法，那么此时就是最大的正方形，返回k**2即可。

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] != 1:                    return False            return True                     for k in range(min(r, c), 0, -1):            for x1 in range(r):                if x1 + k > r:                    break                for y1 in range(c):                    x2, y2 = x1 + k, y1 + k                    if y2 > c:                        break                    if check(x1, y1, x2, y2):                        return k ** 2        return 0

这个算法的时间复杂度是O(n^4)级别的，但是我们提交后，发现也可以通过。

对于这个问题还有一种O(n^3)级别的做法，也非常容易想到，就是通过两个矩阵存储每个点的上面和左边有多少个连续的1，这样我们做check的时候，只要O(1)的时间就可以完成操作，假设我们遍历到的点是(x1,y1)，而此时的边长是k，那么我们只需要检查(x1,y1)、(x1+k,y1)、(x1,y1+k)、(x1+k,y1+k)这四个点对应的存储值的最小值，比较其是不是大于等于k，如果是的话，那么k就是我们要的，否则继续找。

class Solution:    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:        r, c = len(grid), len(grid[0])        h, v = [a[:] for a in grid], [a[:] for a in grid]        for i in range(r):            for j in range(c):                if grid[i][j]:                    if i:                        v[i][j] = v[i-1][j] + 1                    if j:                        h[i][j] = h[i][j-1] + 1        for k in range(min(r, c), 0, -1):            for i in range(r - k + 1):                for j in range(c - k + 1):                    if min(v[i + k - 1][j], v[i + k - 1][j + k - 1], h[i][j + k - 1], h[i + k - 1][j + k - 1]) >= k:                        return k**2        return 0

这么做的话，我们算法的时间复杂度就是O(n^3)。我们还可以从小到大寻找正方形的宽度k。我们首先遍历grid，取h[i][j]和v[i][j]的最小值作为k，然后判断以(i,j)作为右下角点k为宽的正方形是不是合法。如果不合法我们就缩小k继续找，否则我们记录此时的k然后判断下一个点，直到所有点遍历完取k的最大值。

class Solution:    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:        r, c = len(grid), len(grid[0])        h, v = [a[:] for a in grid], [a[:] for a in grid]        for i in range(r):            for j in range(c):                if grid[i][j]:                    if i:                        v[i][j] = v[i-1][j] + 1                    if j:                        h[i][j] = h[i][j-1] + 1        res = 0        for i in range(r):            for j in range(c):                if grid[i][j]:                    s = min(h[i][j], v[i][j])                    while s > res:                        if v[i][j - s + 1] >= s and h[i - s + 1][j] >= s:                            res = max(res, s)                            break                        s -= 1        return res**2

上面这种算法的时间复杂度也是O(n^3)，但是实际测试结果最好。

reference:

我将该问题的其他语言版本添加到了我的

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/97674354 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！