高性能的网站建设指南百度推广代理商

题目链接

Leetcode.1139 最大的以 1 为边界的正方形 Rating ： 1744

题目描述

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

分析：

使用 dp 求解，我们定义 $f(i,j,0)和f(i,j,1)$分别为以点 (i,j)结尾，向左 和 向上的连续 1的个数。

在$f(i,j,0)>0和f(i,j,1)>0$ 的情况下，我们取 $d=min(f(i,j,0),f(i,j,1))$。

遍历$k$ $(0<=k<=d)$，判断 $f(i-k+1,j,0)>=k和f(i,j-k+1,1)>=k$，如果条件成立，说明可以构成一个最后一点是 (i,j)，边长为 k的正方形。

时间复杂度：$O(m\ast n\ast min(m\ast n))$

C++代码：

class Solution {
public:int largest1BorderedSquare(vector<vector<int>>& grid) {int m = grid.size(),n = grid[0].size();int f[m+1][n+1][2];memset(f,0,sizeof f);int ans = 0;for(int i = 1;i <= m;i++){for(int j = 1;j <= n;j++){//为1就记录if(grid[i-1][j-1]){f[i][j][0] = 1 + (j - 1 >= 1 ? f[i][j-1][0] : 0);f[i][j][1] = 1 + (i - 1 >= 1 ? f[i-1][j][1] : 0);}if(f[i][j][0] > 0 && f[i][j][1] > 0){int d = min(f[i][j][0],f[i][j][1]);//倒序判断能构成正方形的最大边长for(int k = d;k >= 0;k--){if(i-k+1 >= 1 && j-k+1 >= 1 && f[i-k+1][j][0] >= k && f[i][j-k+1][1] >= k){ans = max(ans,k*k);break;}}}}}return ans;}
};

Java代码：

class Solution {public int largest1BorderedSquare(int[][] grid) {int m = grid.length,n = grid[0].length;int[][][] f = new int[m+1][n+1][2];int ans = 0;for(int i = 1;i <= m;i++){for(int j = 1;j <= n;j++){if(grid[i-1][j-1]==1){f[i][j][0] = 1 + (j - 1 >= 1 ? f[i][j-1][0] : 0);f[i][j][1] = 1 + (i - 1 >= 1 ? f[i-1][j][1] : 0);}if(f[i][j][0] > 0 && f[i][j][1] > 0){int d = Math.min(f[i][j][0],f[i][j][1]);for(int k = d;k >= 0;k--){if(i-k+1 >= 1 && j-k+1 >= 1 && f[i-k+1][j][0] >= k && f[i][j-k+1][1] >= k){ans = Math.max(ans,k*k);break;}}}}}return ans;}
}