一． 问题描述
现在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
示例:
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4
二． 解题思路
本题思路：本题有两种方法进行求解，暴力法和动态规划的方法进行求解。
第一种：暴力法：
步骤一：依次遍历每一个值，当为0时跳过，如果为1时进行新的遍历
步骤二：新的遍历是将1为左顶点，边长+1，遍历边长内的所有点是不是都为1如果是，则判断temp与边长*边长。直到不满足遍历条件，跳出，返回步骤一。
步骤三：最终输出temp的值。
第二种：动态规划的方法求解（要想到动态规划，把大正方形转换成小正方形的思路来解决）。
步骤一：创建一个初始化为0但维度与matrix相同的矩阵number。将matrix的第一行，第一列全部添加到number中去。
步骤二：遍历matrix矩阵，当值为1时，假设位置（i，j）则在number中相应的位置添加min(number(i-1,j),number(i-1,j-1),number(I,j-1))。
步骤三：最后找出number中最大的值，就是所求的值。
三． 执行结果
第一种方法执行结果
执行用时 :38 ms, 在所有 java 提交中击败了59.92%的用户
内存消耗 :45.3 MB, 在所有 java 提交中击败了64.85%的用户
第二种方法执行结果
执行用时 :1 ms, 在所有 java 提交中击败了99.82%的用户
内存消耗 :20MB, 在所有 java 提交中击败了98.73%的用户
四． Java代码
（1）暴力法：
public int maximalSquare(char[][] matrix) { int number=0; for(int i=0;i<matrix.length;i++) { for(int j=0;j<matrix[0].length;j++) { if(matrix[i][j]==‘0‘) { continue; }else { if(number==0) { number=1; } int time=0; boolean select=true; while(select) { if((i+time)>(matrix.length-2)||(j+time)>(matrix[0].length-2)) { break; } time++; for(int m=i;m<=i+time;m++) { for(int n=j;n<=j+time;n++) { if(matrix[m][n]==‘0‘) { select=false; break; } } if(select==false) { break; } } if(((time+1)*(time+1))>=number&&select!=false) { number=(time+1)*(time+1); } } } } } return number; }
（2）动态规划法
class Solution { public int maximalSquare(char[][] matrix) { if(matrix.length<=0||matrix[0]==null) { return 0; } int temp=0; int [][]number=new int[matrix.length][matrix[0].length]; for(int i=0;i<matrix.length;i++) { if(temp<(matrix[i][0]-‘0‘)) { temp=matrix[i][0]-‘0‘; } number[i][0]=matrix[i][0]-‘0‘; } for(int j=0;j<matrix[0].length;j++) { if(temp<(matrix[0][j]-‘0‘)) { temp=matrix[0][j]-‘0‘; } number[0][j]=matrix[0][j]-‘0‘; } for(int m=1;m<matrix.length;m++) for(int n=1;n<matrix[0].length;n++) { if(matrix[m][n]==‘0‘) { continue; } number[m][n]=Math.min(number[m-1][n], Math.min(number[m-1][n-1], number[m][n-1]))+1; if(temp<number[m][n]) { temp=number[m][n]; } } return temp*temp; } }
原文：https://www.cnblogs.com/xiaobaidashu/p/12095090.html