最大正方形-221

[sl1673495]

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

示例:

输入:

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

输出: 4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-square
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

参考：https://leetcode-cn.com/problems/maximal-square/solution/zui-da-zheng-fang-xing-by-leetcode-solution

可以使用动态规划降低时间复杂度。我们用 dp(i, j) 表示以 (i, j) 为右下角，且只包含 1 的正方形的边长最大值。如果我们能计算出所有 dp(i, j) 的值，那么其中的最大值即为矩阵中只包含 1 的正方形的边长最大值，其平方即为最大正方形的面积。

那么如何计算 dp 中的每个元素值呢？对于每个位置 (i, j)，检查在矩阵中该位置的值：

如果该位置的值是 0，则 dp(i, j)=0，因为当前位置不可能在由 1 组成的正方形中；

如果该位置的值是 1，则 dp(i, j) 的值由其上方、左方和左上方的三个相邻位置的 dp 值决定。具体而言，当前位置的元素值等于三个相邻位置的元素中的最小值加 1，状态转移方程如下：

dp(i, j)=min(dp(i−1, j), dp(i−1, j−1), dp(i, j−1))+1

对于最左列和最上行的状态，我们可以设为基础状态，直接判断值为 1 则最大边长就为 1，值为 0 最大边长就为 0，然后从 x = 1, y = 1 开始继续遍历二维数组做动态规划。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximal-square/solution/zui-da-zheng-fang-xing-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

/**
 * @param {character[][]} matrix
 * @return {number}
 */
let maximalSquare = function (matrix) {
  let maxY = matrix.length
  if (!maxY) return 0
  let maxX = matrix[0].length

  let dp = []
  let max = 0

  let dpBasic = (y, x) => {
    if (matrix[y][x] === "1") {
      max = 1
      dp[y][x] = 1
    } else {
      dp[y][x] = 0
    }
  }
  for (let y = 0; y < maxY; y++) {
    dp[y] = []
    dpBasic(y, 0)
  }
  for (let x = 1; x < maxX; x++) {
    dpBasic(0, x)
  }

  for (let y = 1; y < maxY; y++) {
    for (let x = 1; x < maxX; x++) {
      let val = matrix[y][x]
      if (val === "0") {
        dp[y][x] = 0
      } else {
        let left = dp[y][x - 1]
        let top = dp[y - 1][x]
        let leftTop = dp[y - 1][x - 1]
        dp[y][x] = Math.min(left, top, leftTop) + 1
        max = Math.max(max, dp[y][x])
      }
    }
  }
  return max * max
}