leetcode221 最大正方形

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

示例:

输入: 

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

输出: 4

思路：

dp(i,j) 表示的是必须以ij为右下角，由 1 组成的最大正方形的边长

注：由于dp数组横竖我给长度加了1，导致判断matrix时是i-1和j-1

  

   

    

     

    
    

     

      public class Solution {
     
    
   

    

     

    
    

     
 public int maximalSquare(char[][] matrix) {
     
    
   

    

     

    
    

     
 int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
     
    
   

    

     

    
    

     
 int[][] dp = new int[rows + 1][cols + 1];
     
    
   

    

     

    
    

     
 int maxsqlen = 0;
     
    
   

    

     

    
    

     
 for (int i = 1; i <= rows; i++) {
     
    
   

    

     

    
    

     
 for (int j = 1; j <= cols; j++) {
     
    
   

    

     

    
    

     
 if (matrix[i-1][j-1] == '1'){
     
    
   

    

     

    
    

     

       dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
     
    
   

    

     

    
    

     

       maxsqlen = Math.max(maxsqlen, dp[i][j]);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return maxsqlen * maxsqlen;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/103277586