MENU

【Leetcode】最大的以1为边界的正方形

February 17, 2023 • 题解

【Leetcode】最大的以1为边界的正方形

题目链接:1139. 最大的以 1 为边界的正方形 - 力扣(Leetcode)

给你一个由若干 01 组成的二维网格 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]01

题解

这个题我最开始想的是用搜索来写,但是实际上发现用搜索太复杂了,可以采用DP的方式

我们用两个数组:left和up,分别记录以(i,j)点起始,向左有多少连续的1以及向上有多少连续的一,这样就记录了这个方框的右边和下边的最大可能长度。通过这种方式,我们也可以知道出方框的上边和左边的最大长度: left[i - border + 1]right[j - border + 1],其中 border 是任意可能边长的长度。为了能组成一个正方形,我们需要四条边长度相等,即:取四条边最短的边作为正方形的边长即可。

ACCode

class Solution {
public:
    int largest1BorderedSquare(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        // left[i][j] 以 i, j 为起点,向左最多有多少个 1
        vector<vector<int>> left(m+1, vector<int>(n+1));  
        
        // up[i][j] 以 i,j为起点,向上最多有多少个1
        vector<vector<int>> up(m+1, vector<int>(n+1));

        int maxBorder = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (grid[i-1][j-1] == 1) {
                    left[i][j] = left[i][j-1] + 1;
                    up[i][j] = up[i-1][j] + 1;

                    int border = min(left[i][j], up[i][j]);
                    while (left[i - border + 1][j] < border || 
                           up[i][j - border + 1] < border) {
                        border--;
                    }

                    maxBorder = max(maxBorder, border);
                }
            }
        } 
        return maxBorder * maxBorder;
    }
};
作者:NorthCity1984
出处:https://grimoire.cn/acm/largest-1-bordered-square.html
版权:本文《【Leetcode】最大的以1为边界的正方形》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任