Участник:Rublev.mv/maximal-square — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «* https://leetcode.com/problems/maximal-square/ <code-java> class Solution { public int maximalSquare(char[][] matrix) { if(matrix==null||matrix.…»)
 
(нет различий)

Текущая версия на 16:15, 28 декабря 2020

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