1139. 最大的以 1 為邊界的正方形

思路

枚舉所有的正方形可能，並且使用二維前綴和去加速計算。

前綴和存在傳遞進來的參數當中，因此沒有使用到額外空間， 相比其他做法，有相同的複雜度，以及最好的空間效率。

程式碼

前綴和

class Solution {
public:
    int largest1BorderedSquare(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();

        auto get = [&](int i, int j) -> int {
            return (i < 0 || j < 0) ? 0 : grid[i][j];
        };

        for(int i = 0; i < m; i++) { // 計算二維前綴和
            for(int j = 0; j < n; j++) {
                grid[i][j] += get(i - 1, j) + get(i, j - 1) - get(i - 1, j - 1);
            }
        }
        
        auto sum = [&](int r1, int c1, int r2, int c2) -> int { // 計算區域面積
            return get(r2, c2) - get(r1 - 1, c2) - get(r2, c1 -1) + get(r1 - 1, c1 - 1);
        };

        if(sum(0, 0, m - 1, n - 1) == 0) return 0; // 數組中沒有 1
        int res = 1; // 有一, 答案至少為 1
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) { 
                // 枚舉時從 i + res 開始，假如已經找到大小為 res 的方形，就沒必要再從 2 開始枚舉，而是試著找更大的。
                for(int ni = i + res, nj = j + res, k = res + 1; ni < m && nj < n; ni++, nj++, k++) {
                    // 外圈的數量要等於(邊長 * 4 - 4) = (k - 1) * 4
                    if((sum(i, j, ni, nj) - sum(i + 1, j + 1, ni - 1, nj - 1)) == (k - 1) << 2) {  
                        res = k;
                    }
                }
            }
        }
        return res * res;
    }
};

複雜度分析

• 時間複雜度：$O(mn\min(m, n))$
• 空間複雜度：$O(1)$，使用傳遞的參數作為前綴和的空間。