221. 最大正方形-dp-中等难度

问题描述

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:

输入:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输出: 4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-square

解答

class Solution {
    public int maximalSquare(char[][] matrix) {
        int max = 0, row = matrix.length, i, j;
        if(row == 0)return 0;
        int column = matrix[0].length;
        int[][] dp = new int[row][column];

        for(i=0;i<row;i++){
            for(j=0;j<column;j++){
                if(i!=0 && j!=0){
                    if(matrix[i][j] == '1')dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                }else if(matrix[i][j] == '1')dp[i][j] = 1;
                if(max < dp[i][j])max = dp[i][j];
            }
        }
        // for(i=0;i<row;i++){
        //     for(j=0;j<column;j++){
        //         System.out.print(dp[i][j]+" ");
        //     }
        //     System.out.println();
        // }

        return max*max;
    }
}