java 解法, 执行用时: 4 ms, 内存消耗: 42.3 MB, 提交时间: 2023-02-17 09:29:30

class Solution {
    public int largest1BorderedSquare(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] rs = new int[m][n + 1], cs = new int[n][m + 1];
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j) {
                rs[i][j + 1] = rs[i][j] + grid[i][j]; // 每行的前缀和
                cs[j][i + 1] = cs[j][i] + grid[i][j]; // 每列的前缀和
            }
        for (int d = Math.min(m, n); d > 0; --d) // 从大到小枚举正方形边长 d
            for (int i = 0; i <= m - d; ++i)
                for (int j = 0; j <= n - d; ++j) // 枚举正方形左上角坐标 (i,j)
                    if (rs[i][j + d] - rs[i][j] == d && // 上边
                        cs[j][i + d] - cs[j][i] == d && // 左边 
                        rs[i + d - 1][j + d] - rs[i + d - 1][j] == d && // 下边
                        cs[j + d - 1][i + d] - cs[j + d - 1][i] == d)   // 右边
                        return d * d;
        return 0;
    }
}

golang 解法, 执行用时: 12 ms, 内存消耗: 6.4 MB, 提交时间: 2023-02-17 09:29:01

func largest1BorderedSquare(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    rs := make([][]int, m)
    for i := range rs {
        rs[i] = make([]int, n+1)
    }
    cs := make([][]int, n)
    for i := range cs {
        cs[i] = make([]int, m+1)
    }
    for i, row := range grid {
        for j, x := range row {
            rs[i][j+1] = rs[i][j] + x // 每行的前缀和
            cs[j][i+1] = cs[j][i] + x // 每列的前缀和
        }
    }
    for d := min(m, n); d > 0; d-- {
        for i := 0; i <= m-d; i++ {
            for j := 0; j <= n-d; j++ {
                if rs[i][j+d]-rs[i][j] == d && // 上边
                   cs[j][i+d]-cs[j][i] == d && // 左边
                   rs[i+d-1][j+d]-rs[i+d-1][j] == d && // 下边
                   cs[j+d-1][i+d]-cs[j+d-1][i] == d {  // 右边
                    return d * d
                }
            }
        }
    }
    return 0
}

func min(a, b int) int { if b < a { return b }; return a }

python3 解法, 执行用时: 156 ms, 内存消耗: 15.4 MB, 提交时间: 2023-02-17 09:28:44

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        rs = [list(accumulate(row, initial=0)) for row in grid]  # 每行的前缀和
        cs = [list(accumulate(col, initial=0)) for col in zip(*grid)]  # 每列的前缀和
        for d in range(min(m, n), 0, -1):  # 从大到小枚举正方形边长 d
            for i in range(m - d + 1):
                for j in range(n - d + 1):  # 枚举正方形左上角坐标 (i,j)
                    # 上 左 下 右 四条边 1 的个数均为 d
                    if rs[i][j + d] - rs[i][j] == d and \
                       cs[j][i + d] - cs[j][i] == d and \
                       rs[i + d - 1][j + d] - rs[i + d - 1][j] == d and \
                       cs[j + d - 1][i + d] - cs[j + d - 1][i] == d:
                        return d * d
        return 0

python3 解法, 执行用时: 104 ms, 内存消耗: 15.3 MB, 提交时间: 2023-02-17 09:27:15

'''
前缀和 + 枚举
我们可以使用前缀和的方法预处理出每个位置向下和向右的连续 1 的个数，
记为 down[i][j] 和 right[i][j]。

然后我们枚举正方形的边长 k，从最大的边长开始枚举，然后枚举正方形的左上角位置 (i,j)，如果满足条件，即可返回k^2
'''

class Solution:
    def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        down = [[0] * n for _ in range(m)]
        right = [[0] * n for _ in range(m)]
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if grid[i][j]:
                    down[i][j] = down[i + 1][j] + 1 if i + 1 < m else 1
                    right[i][j] = right[i][j + 1] + 1 if j + 1 < n else 1
        for k in range(min(m, n), 0, -1):
            for i in range(m - k + 1):
                for j in range(n - k + 1):
                    if down[i][j] >= k and right[i][j] >= k and right[i + k - 1][j] >= k and down[i][j + k - 1] >= k:
                        return k * k
        return 0