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

本题直观上来说可以用暴力枚举，每次遍历到一个1，就扫描看看以它形成的正方形最大能多大既可。
但是注意由于我们遍历是从左到右，从上到下，因此每次形成的正方形也只要往这个方向遍历既可，因为如果需要往左往上遍历成一个正方形，那之前就一定已经遍历过了。所以不需要再往那个方向遍历了。

代码如下：

public class Solution {
    public int maximalSquare(char[][] matrix) {
        int row = matrix.length;
        if(row == 0) return 0;
        int column = matrix[0].length;
        int maxlen = 0;
        for(int i = 0; i < row ;i++ ){
            for(int j = 0;j < column;j++ ){
                
                if(matrix[i][j] == '1'){
                    boolean flag = true;
                    int squareLength = 1;
                    while(squareLength + i < row && squareLength + j < column && flag){
                        for(int k = i; k <= squareLength + i; k++ ){
                            if(matrix[k][squareLength+j] == '0'){
                                flag = false;
                                break;
                            }
                        }
                        for(int k = j; k <= squareLength + j; k++ ){
                            if(matrix[squareLength+i][k] == '0'){
                                flag = false;
                                break;
                            }
                        }
                        if(flag) 
                        squareLength++;
                    }
                    if(squareLength> maxlen){
                        maxlen = squareLength;
                        break;
                    } 
                        
                     
                }
                
            }
        }
        return maxlen*maxlen;
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-square
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。