解法都在代码里,不懂就留言或者私信
class Solution {
/**本题一看就是典型的动态规划,要找以每个点为右下角的正方形的面积,然后取最大的
这个题要注意找规律,我找到的规律如下:1.以第一行为右下角的,因为正方形是边长相同的,所以第一行为右下角最大正方形只能是自己,自己是1就是1,不是1就是0
2. 以第一列为右下角的也是一样。
3. 以普通位置为右下角的最大正方形,首先看自己是不是1,如果自己不是1,那就肯定是0,如果自己是1,取它的左上、左、上三个点的最小面积,加1就是它的解
自己可以多画几个二维矩阵找找规律
*/
public int maximalSquare(char[][] matrix) {
/**空矩阵的校验,健壮性校验 */
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
/**如果矩阵只有一个数字,那就是0最大面积就是0,是'1'最大面积就是1*/
if(matrix.length == 1 && matrix[0].length == 1) {
return matrix[0][0] == '1'? 1 : 0;
}
/**其他的不过多枚举了,直接动态规划解吧,dp[i][j]代表以(i,j)为右下角的最大正方形的边长*/
int[][] dp = new int[matrix.length][matrix[0].length];
/**定义最大值变量 */
int maxArea = 0;
/**初始化第一行和第一列*/
for(int j = 0; j < dp[0].length; j++) {
dp[0][j] = matrix[0][j] == '1'? 1 : 0;
/**这里其实是dp[0][j]* dp[0][j],反正最大就是1,懒得写了 */
maxArea = Math.max(maxArea, dp[0][j]);
}
for(int i = 1; i < dp.length; i++) {
dp[i][0] = matrix[i][0] == '1'? 1 : 0;
/**这里其实是dp[i][0]* dp[i][0],反正最大就是1,懒得写了 */
maxArea = Math.max(maxArea, dp[i][0]);
}
/**初始化普通位置 */
for(int i = 1; i < dp.length; i++) {
for(int j = 1; j < dp[i].length; j++) {
if(matrix[i][j] == '1') {
dp[i][j] = matrix[i][j] == '1'? Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1 : 0;
maxArea = Math.max(maxArea, dp[i][j]*dp[i][j]);
}
}
}
return maxArea;
}
}
相信我这就是最优解,矩阵就是m*n,你不过完能知道答案吗