第221题：最大正方形

一． 问题描述

现在一个由 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;
    }
}