212-最大正方形.md

题目描述

最大正方形

题目简述

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

示例 1

• 输入：

matrix = [
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]]

• 输出：4

分类

中等 动态规划

思路

动态规划

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function(matrix) {
  let max = 0
  const dp = Array.from({ length: matrix.length }, () => new Array(matrix[0].length).fill(0))
  for (let i = 0; i < matrix.length; i ++) {
    for (let j = 0; j < matrix[0].length; j ++) {
      if (matrix[i][j] === '1') {
        // 边界
        if (!i || !j) {
          dp[i][j] = 1
        } else {
          if(dp[i - 1][j] === dp[i][j - 1]) {
            if (dp[i - 1][j - 1] >= dp[i - 1][j]) {
              dp[i][j] = dp[i - 1][j] + 1
            } else {
              dp[i][j] = dp[i - 1][j]
            }
          } else {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1
          }
        }
        max = Math.max(max, dp[i][j])
      }
    }
  }
  return max * max
};

• 问题分析
  • 矩阵中正方形的特殊性很容易观察到，一个n x n 的正方形中一定有(n - 1) x (n - 1)的正方形。
  • 我们先声明一个和matrix行列相等的矩阵dp,用于储存该位置最大的正方形边长，i为行号、j为列号。
  • 如何根据之前的条件判断当前位置的最大正方形呢？分为以下几种情况
    • 首先是边界情况，首行和首列的位置如果在matrix中为'1'，则为1，自己就是最大的正方形。
    • 如下，绿色边框为dp[i][j - 1]的最大正方形，蓝色边框为dp[i - 1][j]的最大正方形，黄色底色为dp[i - 1][j - 1]的最大正方形。
    • 当绿色和蓝色边框边长相等时，只需要判断黄色底色边框长度是否大于等于绿色（蓝色）边长，如果不是（参考上图），该位置最大正方形边长为dp[i][j] = dp[i - 1][j]，如果是（参考下图），则该位置最大正方形边长为dp[i][j] = dp[i - 1][j] + 1。
    • 蓝色和绿色边长不相等时，该位置边长为两者边长较小值+1，即dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1
  • 在不断计算出位置结果时，使用max去比较拿到最大值，最终max * max即为最大正方形面积。
  • 遍历顺序：根据我们的方法可以得出，我们整个方向需要从左上往右下，所以只需要i、j由小往大即可。