LeetCode 221. 最大正方形

题目描述

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

示例说明

输入：

[ ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"] ]

输出： 4

解释： 右下角存在一个 2×2 的全为 '1' 的正方形，面积为 4。

解题思路

核心观察

要判断以 (i, j) 为右下角的最大正方形边长，关键在于它左、上、左上三个方向能构成的最大正方形边长。这天然适合使用动态规划。

状态定义与转移

设 dp[i][j] 表示以 (i, j) 为右下角的最大正方形的边长。

• 如果 matrix[i][j] == '0'，则 dp[i][j] = 0
• 如果 matrix[i][j] == '1'，则 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

边界处理上，第 0 行和第 0 列可直接初始化为 matrix[i][j] - '0'。遍历时记录 maxSide，最终返回 maxSide * maxSide。

代码实现

下面分别给出 Java 的标准二维 DP 实现和 Go 的空间优化版本。

Java 实现

class Solution {
    public int maximalSquare {
         (matrix ==  || matrix.length ==  || matrix[].length == ) {
             ;
        }
           matrix.length, n = matrix[].length;
        [][] dp =  [m][n];
           ;
         (   ; i < m; i++) {
             (   ; j < n; j++) {
                 (matrix[i][j] == ) {
                     (i ==  || j == ) {
                        dp[i][j] = ;
                    }  {
                        dp[i][j] = Math.min(Math.min(dp[i - ][j], dp[i][j - ]), dp[i - ][j - ]) + ;
                    }
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }
         maxSide * maxSide;
    }
}