Leetcode221. 最大正方形

2021年8月13日 254点热度 2人点赞 0条评论

题目描述

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

示例 1:

img

输入:matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出:4

示例 2:

img

输入: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'

解题思路

这道题首先可以用暴力的方法来求解。比如用两层循环来扫描矩阵中的每一个元素,然后求出以[i,j]元素为左上角元素的最大正方形的面积,然后记录下这个值。当扫描完整个数组后,就可以求出最终的最大正方形面积。但是这个方法的复杂度非常高。

这道题更优的解法是运用动态规划的方法(有“最大”两个字嘛)。我们可以用 dp(i,j) 表示以 (i,j) 为右下角,且只包含 1 的正方形的边长最大值。如果我们能计算出所有 dp(i,j) 的值,那么其中的最大值即为矩阵中只包含 1 的正方形的边长最大值,其平方即为最大正方形的面积。然后需要计算dp数组 中的每个元素值:

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

  • 如果该位置的值是 1,则 $dp(i,j)$ 的值由其上方、左方和左上方的三个相邻位置的值决定:

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

接下来就是最为困难的过程,如何理解上述的公式呢?

通过观察,会发现以下规律:

  • 若形成正方形(非单 1),以当前元素为右下角的视角看,则需要:当前格、上、左、左上都是 1
  • 可以换个角度:当前格、上、左、左上都不能受 0 的限制,才能成为正方形

上面详解了 三者取最小 的含义:

图 1:受限于左上的 0
图 2:受限于上边的 0
图 3:受限于左边的 0
数字表示:以此为正方形右下角的最大边长
黄色表示:格子 ? 作为右下角的正方形区域

进一步的说,可以分两种情况来进行分析:

  • 假设三者最小为 0 ,那么根据上图,这个位置的上方、左方和左上方的三个相邻位置的值至少有一个会为 0 ,那么当这个位置的值为 “1” ,自然以这个位置为右下角的最大正方形边长会为 1 ;
  • 假设三者最小为 1 ,那么根据上图,这个位置的上方、左方和左上方的三个相邻位置的值至少有一个会为 1 ,这三个位置的dp值都会大于等于 1 。那么当这个位置的值为 “1” ,自然以这个位置为右下角的最大正方形边长会为 2 。如果假设以这个位置为右下角的最大正方形边长大于 2 ,那么不会满足条件的,因为总会有一个方向的某个格子的值会为 ”0“(这个位置的上方、左方和左上方的三个相邻位置的值至少有一个会为 1);

上面是两种比较简单的情况,其他更大的数也是同理。

总结以下,这道题运用动态规划最大的困难是:

  • dp[i][j]的具体含义;
  • 状态转移方程的理解;

具体细节见参考代码。

参考代码

int maximalSquare(vector<vector<char>>& matrix){
    if(matrix.empty()) return 0;

    int ans = 0;
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for(int i = 0; i < m; ++i){
        for(int j = 0; j < n; ++j){
            if(matrix[i][j] == '1'){
                dp[i + 1][j + 1] = min(dp[i][j + 1], min(dp[i + 1][j], dp[i][j])) + 1;
                ans = max(ans, dp[i + 1][j + 1]);
            }
        }
    }

    return ans * ans;
}

复杂度分析

时间复杂度:$O(mn)$,其中 $m$ 和 $n$​ 是矩阵的行数和列数

空间复杂度:$O(mn)$,其中 $m$ 和 $n$ 是矩阵的行数和列数

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论