LeetCode-1139. 最大的以 1 为边界的正方形【前缀和，矩阵】

题目描述：

给你一个由若干 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
https://leetcode.cn/problems/largest-1-bordered-square/

解题思路一：前缀和。前缀和来记录边长。

class Solution {
public:int largest1BorderedSquare(vector<vector<int>> &grid) {int m = grid.size(), n = grid[0].size();vector<vector<int>> rs(m, vector<int>(n + 1)), cs(n, vector<int>(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 = min(m, n); d; --d) // 从大到小枚举正方形边长 dfor (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;}
};

时间复杂度：O(mnmin(m,n))其中 m和 n分别为 grid的行数和列数。
空间复杂度：O(mn)

解题思路二：0

解题思路三：0

参考链接