1. 题目描述

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

示例 1：
221. 最大正方形 - 图1

  1. 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
  2. 输出：4

示例 2：
221. 最大正方形 - 图2

  1. 输入：matrix = [["0","1"],["1","0"]]
  2. 输出：1

示例 3：

  1. 输入：matrix = [["0"]]
  2. 输出：0

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j] 为 '0' 或 '1'

    2. 解题思路

    对于这道题目，我们可以使用动态规划来解决，这里我们需要初始化与一个dp数组，dp[i][i]表示以 (i, j)为右下角，且只包含 1 的正方形的边长最大值。我们只需要遍历这个二维矩阵，计算机每个dp的值，选出最大值，即正方形的最大边长，最后返回这个正方形的面积即可。

计算dp的每个值有以下规则：

  • 如果当前的值为0，此时该点不存在于正方形中，直接给dp[i][j]赋值为0；
  • 如果当前的值为1，dp[i][j]的值由其上、左、左上的三个值的最小值决定，所以其状态转移方程是：
    1. dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
    除此之外，我们还需要考虑二维矩阵的最左边一列和最上面一行，如果值是1，就直接将dp[i][j]赋值为1。

复杂度分析：

  • 时间复杂度：O(mn)，其中 m 和 n 是二维矩阵的行数和列数。我们需要遍历二维矩阵中的每个元素来计算 dp 的值。

  • 空间复杂度：O(mn)，其中 m 和 n 是二维矩阵的行数和列数。我们创建了一个和原始矩阵大小相同的数组 dp 来保存当前正方形的最大边长。

    3. 代码实现

    1. /**
    2. * @param {character[][]} matrix
    3. * @return {number}
    4. */
    5. var maximalSquare = function(matrix) {
    6.   const m = matrix.length, n = matrix[0].length
    7.   let res = 0
    8.   if(!matrix || m === 0 || n === 0){
    9.       return 0
    10.   }
    12.   let dp = new Array(m)
    13.   for(let i = 0; i < m; i++){
    14.       dp[i] = new Array(n).fill(0)
    15.   }
    17.   for(let i = 0; i < m; i++){
    18.       for(let j = 0; j < n; j++){
    19.           if(matrix[i][j] === '1'){
    20.               if(i === 0 || j === 0){
    21.                   dp[i][j] = 1
    22.               }else{
    23.                   dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
    24.               }
    25.               res = Math.max(dp[i][j], res)
    26.           }
    27.       }
    28.   }
    29.   return res * res
    30. };

    4. 提交结果

    image.png