【动态规划Ⅴ】二维数组的动态规划——0/1矩阵、最大正方形

二维数组的动态规划——0/1矩阵、最大正方形

• 最大正方形
• • 1277. 统计全为 1 的正方形子矩阵
  • 221. 最大正方形
  • 01矩阵
  • • 542. 01 矩阵

      最大正方形

      下面两个题目是非常相似的，只是一个统计正方形数目，一个统计最大正方形的面积。

      1277. 统计全为 1 的正方形子矩阵

      1277. 统计全为 1 的正方形子矩阵

      给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

      首先，如果矩阵matrix[i][j] = 1，那么就是一个大小为1的正方形。假设用二维数组dp进行统计，dp[i][j]即以matrix[i][j]为右下顶点的全是1组成的正方形的个数【其实也是以matrix[i][j]为右下点的全是由1组成的正方形的最大边长，最大正方形】。

      我们从大小为1的正方形开始，要解决的问题是这个正方形如何扩大？根据官方题解中的图，很好理解，dp[i][j]与其上面、左边和左上三个角，且由其中最小的一个决定，即dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1, matrix[i][j] +1

      

      可以先处理第一列和第一行，只要matrix[i][j]为1，dp[i][j]就等于1，同时统计的正方形子矩阵数量+1。完整java代码如下：

      class Solution {
          public int countSquares(int[][] matrix) {
              int rows = matrix.length, cols = matrix[0].length;
              int[][] count = new int[rows][cols];
              int sum = 0;
              //单独处理
              for(int i = 0; i  c)
                  minCur = c;
              return minCur;
          }
      }
      

      221. 最大正方形

      221. 最大正方形

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

      这个题目和上面是类似的，上面的dp[i][j]是以matrix[i][j]为右下角的，全部由1组成的正方形的数量，其实也就是以matrix[i][j]为右下角的正方形的最大边长。只是这个题目找的是dp[i][j]中的最大值。 需要注意的是，这个题目中matrix[i][j]是char类型的，是’0’'1’字符而不是数字。

      完整java代码如下：

      class Solution {
          public int maximalSquare(char[][] matrix) {
              int ansMax = 0;
              int rows = matrix.length, cols = matrix[0].length;
              int[][] count = new int[rows][cols];
              for(int i = 0; i  count[i][j] ? ansMax : count[i][j];
                  }
              }  
              //返回的是面积     
              return ansMax*ansMax;
          }
      }
      

      01矩阵

      542. 01 矩阵

      542. 01 矩阵

      给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

      两个相邻元素间的距离为 1 。

      理解题意，是要我们找mat[i][j]离其周围的最近的0的距离，这里的周围是四个方向，上边[i-1][j]、下边[i+1][j]、左边[i][j-1]、右边[i][j+1]。如果用dp[i][j]记录这个最近距离，相当于dp[i][j] = min( dp[i-1][j], dp[i+1][j], dp[i][j-1], dp[i][j+1]) + 1。

      这个题要结果的问题是如何更新这个dp？遍历（逐个更新其元素）一个二维数组需要两成循环，横纵坐标能够表示两个遍历方向，我们需要四个，那么进行两次遍历更新，一个往左下，一个往右上【当然这里选择右下和左上的方向一样的】。代码如下：

      class Solution {
          public int[][] updateMatrix(int[][] mat) {
              int rows = mat.length, cols = mat[0].length;
              int[][] distance = new int[rows][cols];
              for (int i = 0; i  0)
                          distance[i][j] = Math.min(distance[i][j], distance[i-1][j] + 1);
                      if(j > 0)
                          distance[i][j] = Math.min(distance[i][j], distance[i][j-1] + 1);
                  }
              }
      		//往右上的方向更新dp
              for(int i = rows - 1; i >= 0; i--){
                  for(int j = cols - 1; j >= 0; j--){
                      if(i