[leetcode每日一题]2.17

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

难度中等192

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

Solution

先说说我的笨办法吧，从最大的可能边长开始，依次列举可能的矩形左上角位置。直到寻找到可能的位置。

class Solution {
public:
    int largest1BorderedSquare(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int mx = min(m, n);
        bool flag = true;
        for(int i = mx;i > 0;i--){
            // 横边
            for(int x = 0;x<=m-i;x++){
                for(int y = 0;y<=n-i;y++){
                    for(int k = 0;k < i;k++){
                        if(!grid[x+k][y] || !grid[x+i-1][y+k] || !grid[x+i-1-k][y+i-1] || !grid[x][y+i-1-k]){
                            flag = false;
                            break;
                        }
                    }
                    if(flag)return i*i;  
                    flag = true;
                }
            }
        }
        return 0;
    }
};

但是这样肯定是重复遍历了很多次，所以可以使用动态规划优化。

class Solution:
    def largest1BorderedSquare(self, grid):
        m, n = len(grid), len(grid[0])
        left = [[0] * (n + 1) for _ in range(m + 1)]
        up = [[0] * (n + 1) for _ in range(m + 1)]
        maxBorder = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if grid[i - 1][j - 1]:
                    left[i][j] = left[i][j - 1] + 1
                    up[i][j] = up[i - 1][j] + 1
                    border = min(left[i][j], up[i][j])
                    while left[i - border + 1][j] < border or up[i][j - border + 1] < border:
                        border -= 1
                    maxBorder = max(maxBorder, border)
        return maxBorder ** 2

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/largest-1-bordered-square/solution/zui-da-de-yi-1-wei-bian-jie-de-zheng-fan-74ce/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。