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

问题描述

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

给你一个由若干 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

解题思路

利用前缀和来简化满足正方形条件的计算，枚举正方形边长，找到最大的l，再和已经得出的结果进行比较。

代码

class Solution {
  public:
    int largest1BorderedSquare(vector<vector<int>> &grid) {
        // 前缀和
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> sum_row(m, vector<int>(n + 1, 0)); // 每行前缀和
        vector<vector<int>> sum_col(m + 1, vector<int>(n, 0)); // 每列前缀和
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 1; j <= n; j++) {
                sum_row[i][j] = sum_row[i][j - 1] + grid[i][j - 1];
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j < n; j++) {
                sum_col[i][j] = sum_col[i - 1][j] + grid[i - 1][j];
            }
        }
        int res = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                for (int l = res + 1; l <= std::min(i, j); l++) { // 直接从res开始
                    if (sum_col[i][j - 1] - sum_col[i - l][j - 1] == l && sum_row[i - 1][j] - sum_row[i - 1][j - l] == l && sum_col[i][j - l] - sum_col[i - l][j - l] == l && sum_row[i - l][j] - sum_row[i - l][j - l] == l)
                        res = std::max(l, res);
                }
            }
        }
        return res * res;
    }
};