算法练习第二十七题

221. 最大正方形

难度中等486收藏分享切换为英文关注反馈
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
示例:
输入:

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

输出: 4

解题思路，设置一个二维数组用于标记某一个点的对应位置的的最大边长。从第一个点开始，只要出现上，左，左上三个位置均为1的情况，即类加1。

设置标记数组，由于循环是依次类加的，当遍历每一个点的时候，都取出当前点的其他三个相邻三个位置的值，取最小作为边长，当整个数组遍历完成后，以某个点为基准点的类加结果即为边长最大值。

class Solution {
      public int maximalSquare(char[][] matrix) {
          // 当数组为null，数组长度为0时直接返回面级为0
          if(matrix==null || matrix.length==0 || matrix[0].length==0) return 0;
          int width = matrix[0].length;
          int height = matrix.length;
          int maxSide = 0;
          int dp[][] = new int[height+1][width+1]; 
          // 遍历二维数组
          for(int i=0;i<height;i++){
              for(int j=0;j<width;j++){
                  if(matrix[i][j]=='1'){
                      // 设置标记数组对应位置所找到的最大长度，由于循环内判断，当有连续时，一直类加直到找到第一个不是0的位置
                      dp[i+1][j+1] = Math.min(Math.min(dp[i + 1][j], dp[i][j + 1]), dp[i][j]) + 1;
                      System.out.println(dp[i+1][j+1]);
                      maxSide = Math.max(dp[i+1][j+1],maxSide);
                  }
              }
          }
          return maxSide*maxSide;
    }
}