题目
在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。
示例:
1
2
3
4
5
6
7
8 输入:
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
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
暴力破解
将题目转换为:假设输入矩阵$n*n$,找到$m<n$个连续的数$idx_1…idx_m$,使得
1 | for i in range (idx_1, idx_m): |
找到最大m。那么暴力破解可以遍历所有可能的取值,并判断上述条件是否成立。每判断一次需要$O(N^2)$,需要判断$O(N^2)$组数,因此时间复杂度$O(N^4)$。
官方给出的暴力解法:以一个元素为右下角元素拓展,遍历所有的元素,计算以每个元素为右下角的最大正方形面积。时间复杂度与上述方法相等。
这中间存在大量重复计算,可以进行动态规划。
动态规划
对于每个元素,假设它为正方形的右下角元素,并记以当前位置为右下角的最大正方形边长为$dp[i][j]$,那么想要知道$dp[i][j]$的值,必须向左上扩张,即:左、上、左上侧元素都是1,$dp[i][j]$才能加一。
在这里,我们给出一个直观的结论:$dp[i][j]$的值取决与与其相邻的三个元素的最小值,状态转移方程为:
$$
dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
$$
特别地,对第一行元素,它们的值只能为1,第一列元素的值也只能为1。
特殊输入:
1 | [['0']] 输出 0 |
代码:
1 | class Solution { |
- 时间复杂度$O(MN)$
- 空间复杂度$O(MN)$
还可以在原地计算,优化空间复杂度
1 | class Solution { |
- 空间复杂度$O(1)$