题目

描述

• 给定一个由'0'和'1'组成的2维矩阵，返回该矩阵中最大的由'1'组成的正方形的面积

方法一

思路

• 题目要求找到最大全为1的正方形范围，最容易想到的方法就是一个一个正方形进行遍历，先从最大的正方形开始，逐渐减短边长直到找到全为1的正方形区域。

具体步骤

• 1.取矩阵的短边为正方形的初始边长；
• 2.遍历整个矩阵寻找满足该边长以及全为一的正方形；
• 3.找到，则返回正方形面积；
• 4.找不到，边长减一，返回步骤2；

  import java.util.*;
  public class Solution {
  /**
  * 最大正方形
  * @param matrix char字符型二维数组 
  * @return int整型
  */
  public int solve (char[][] matrix) {
     // write code here
     int res = 0;
     // 取边长为最短的一边
     int sideLength = matrix.length < matrix[0].length ?
         matrix.length : matrix[0].length;
     // 从最大正方形边长开始遍历
     while(sideLength > 0 ){
         for (int i = 0;i + sideLength <= matrix.length; ++i){
             for (int j = 0;j + sideLength <= matrix[0].length; ++j){
                 // 正方形左上角的点
                 if (matrix[i][j] == '1'){
                     boolean flag = true;
                     // 遍历整个正方形区域内的所有点，判断是否能够构成一个正方形
                     for (int m = 0;m < sideLength;++m){
                         for (int n = 0;n < sideLength;++n){
                             if (matrix[i+m][j+n] == '0'){
                                 flag = false;
                                 break;
                             }
                         }
                     }
                     // 全为1，即为最大边长
                     if (flag){
                         return sideLength*sideLength;
                     }
                 }
             }
         }
         --sideLength;
     }
     return res;
  }
  }

• 时间复杂度为:,令c = min{m,n},则对于整个while循环的复杂度为
• 空间复杂度：,常数级空间复杂度。

方法二

思路

方法一多次遍历整个矩阵，中间有很多的冗余数据，为了降低时间复杂度，可以考虑使用动态规划的方法，使用二维数组记录已经得到的正方形边长。

具体步骤

• 定义二维数组dp[][]，dp[i][j]表示matrix[i][j]为正方形右下角的最大的正方形边长；
• 而当matrix[i][j]=1时，表示该节点可以成为一个正方形的组成部分，且当前已知的正方形边长为1；
• 当以这个节点为正方形的右下角开始扩展时，需要向上，向左以及向其左对角进行查询，看能不能组成一个更大的正方形；
• 当上述三个位置均满足构成正方形的条件时，则以(i,j)为右下角的正方形可以扩展；
• 递推公式如下：
  
• 见下图的例子
  
• 代码如下：

  import java.util.*;
  public class Solution {
    /**
     * 最大正方形
     * @param matrix char字符型二维数组 
     * @return int整型
     */
    public int solve (char[][] matrix) {
        int[][] dp = new int[matrix.length+1][matrix[0].length+1];
        int side = 0;
        for (int i = 1; i <= matrix.length; ++i) {
            for (int j = 1; j <= matrix[0].length; ++j) {
                if (matrix[i - 1][j - 1] == '1') {
                    //递推公式
                    dp[i][j] = Math.
                    min(dp[i - 1][j],Math.
                        min(dp[i - 1][j - 1], dp[i][j - 1])) + 1;
                    //记录最大的边长
                    side = Math.max(side, dp[i][j]);
                }
            }
        }
        //返回正方形的面积
        return side * side;
    }
  }

• 时间复杂度：,遍历整个二维数组；
• 空间复杂度：,创建了一个辅助二维数组，用于记录每个节点所能构成的正方形的最大边长。