题目链接

LeetCode

题目描述

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

示例 1：

221. 最大正方形 - 图1

输入： matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]
输出： 4

示例 2：

221. 最大正方形 - 图2

输入： matrix = [[“0”,”1”],[“1”,”0”]]
输出： 1

示例 3：

输入： matrix = [[“0”]]
输出： 0

提示：

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

    解题思路

    方法一：动态规划

我们用 dp(i,j) 表示以 (i, j) 为右下角，且只包含 1 的正方形的边长最大值。如果我们能计算出所有 dp(i,j) 的值，那么其中的最大值即为矩阵中只包含 11 的正方形的边长最大值，其平方即为最大正方形的面积。

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

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

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

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

如果读者对这个状态转移方程感到不解，可以参考 1277. 统计全为 1 的正方形子矩阵的官方题解，其中给出了详细的证明。

此外，还需要考虑边界条件。如果 i 和 j 中至少有一个为 0，则以位置 (i,j) 为右下角的最大正方形的边长只能是 1，因此 dp(i,j)=1。

下图也给出了计算 dp 值的过程。
221. 最大正方形 - 图3

  1. class Solution {
  2. public:
  3.     int maximalSquare(vector<vector<char>>& matrix) {
  4.         if(matrix.size()||matrix[0].size())
  5.             return 0;
  6.         int rows = matrix.size();
  7.         int cols = matrix[0].size();
  8.         vector<vector<int>> dp(rows,vector<int>(cols,0));
  9.         int res = 0;
  10.         for(int i=0;i<rows;i++){
  11.             for(int j=0;j<cols;j++){
  12.                 if(matrix[i][j]=='1'){
  13.                     if(i==0||j==0){
  14.                         dp[i][j] = 1;
  15.                     }else{
  16.                         dp[i][j] = min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
  17.                     }
  18.                     res = max(res,dp[i][j]);
  19.                 }
  20.             }
  21.         }
  22.         return res*res;
  23.     }
  25. };
class Solution {
    public int maximalSquare(char[][] matrix) {
        int[][] dp = new int[matrix.length][matrix[0].length];
        int res = 0;
        for(int i=0;i<matrix.length;++i){
            for(int j=0;j<matrix[0].length;++j){
                if(i==0||j == 0){
                    dp[i][j] = matrix[i][j] == '0'?0:1;
                }else{
                    dp[i][j]=matrix[i][j]=='0'?0:1+Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]);
                }
                res = Math.max(res,dp[i][j]);
            }
        }
        return res*res;
    }
}
  • 时间复杂度 O(nm)
  • 空间复杂度 O(nm)