1139. 最大的以 1 为边界的正方形

题目链接：1139. 最大的以 1 为边界的正方形

方法：二维数组前缀和

解题思路

假设以 \((i, j)\) 为左上角端点的正方形网格边长为 \(d\)，则该正方形的四条边 \(up、down、left、right\) 均为\(d\)，两者为充分必要条件。根据二维前缀和运算可得：

up = s[i][j + d] - s[i - 1][j + d] - s[i][j - 1] + s[i - 1][j - 1];
down = s[i + d][j + d] - s[i + d - 1][j + d] - s[i + d][j - 1] + s[i + d - 1][j - 1];
left = s[i + d][j] - s[i + d][j - 1] - s[i - 1][j] + s[i - 1][j - 1];
right = s[i + d][j + d] - s[i + d][j + d - 1] - s[i - 1][j + d] + s[i - 1][j + d - 1];
// 即满足 up == d && down == d && left == d && right == d

由于要求 \(d\) 最大，则从大到小遍历 \(d\)，再遍历网格中的点，若存在符合条件的点，返回当前网格元素数量。

代码

class Solution {
public:
    int largest1BorderedSquare(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int s[n + 1][m + 1]; memset(s, 0, sizeof(s));
        // s[0][0...m] 和 s[0...n][0] 中的元素均为0，为了方便边界前缀和的计算
        // s[i][j] 表示以grid[i-1][j-1]为右下端点的所有左上放元素的和
        for (int i = 1; i <= n; i ++ ) 
            for (int j = 1; j <= m; j ++ ) 
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + grid[i - 1][j - 1];

        for (int d = min(n, m) - 1; d >= 0 ; d -- ){
            for (int i = 1; i + d <= n; i ++ ) {
                for (int j = 1; j + d <= m; j ++ ) {
                    int up = s[i][j + d] - s[i - 1][j + d] - s[i][j - 1] + s[i - 1][j - 1];
                    int down = s[i + d][j + d] - s[i + d - 1][j + d] - s[i + d][j - 1] + s[i + d - 1][j - 1];
                    int left = s[i + d][j] - s[i + d][j - 1] - s[i - 1][j] + s[i - 1][j - 1];
                    int right = s[i + d][j + d] - s[i + d][j + d - 1] - s[i - 1][j + d] + s[i - 1][j + d - 1];
                    if (up + down + left + right == 4 * (d + 1)) return (d + 1) * (d + 1);
                }
            }
        } 
        return 0;
    }
};

复杂度分析

时间复杂度：\(O(nm*min(n, m))\)，\(n\) 和 \(m\)分别为 \(grid\) 二维数组行和列的长度；
空间复杂度：\(O(nm)\)。