leetcode-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

方法有很多，这里只列举一种最容易理解的思路

class Solution {
    public int maximalSquare(char[][] matrix) {
    if(matrix.length==0){return 0;}
    int[][]nums=new int[matrix.length][matrix[0].length];
    for(int i=0;i<matrix.length;i++){
        for(int j=0;j<matrix[0].length;j++){
            if(j==0){nums[i][j]=matrix[i][j]-'0';}
            else if(matrix[i][j]=='0'){nums[i][j]=0;}
            else{nums[i][j]=nums[i][j-1]+1;}
        }
    }
    int result=0;
    for(int i=0;i<nums.length;i++){
        for(int j=0;j<nums[0].length;j++){
            int min=nums[i][j];
            for(int k=i;k>=0;k--){
                 min=Math.min(min,nums[k][j]);
                if(nums[k][j]==0||i-k+1>min){
                    break;
                }else{
                    int length=i-k+1;
                    result=Math.max(result,length*length);
                }
            }
        }
    }
    return result;
    }
    }