221. 最大正方形
链接:https://leetcode-cn.com/problems/maximal-square/
动态规划
我们用一个例子来解释这个方法:
0 1 1 1 0
1 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 0 1 1 1
我们用 0 初始化另一个矩阵 dp,维数和原始矩阵维数相同;
dp(i,j) 表示的是由 1 组成的最大正方形的边长;
从 (0,0)开始,对原始矩阵中的每一个 1,我们将当前元素的值更新为
dp(i, j)=min(dp(i−1, j), dp(i−1, j−1), dp(i, j−1))+1
我们还用一个变量记录当前出现的最大边长,这样遍历一次,找到最大的正方形边长 maxsqlen,那么结果就是 maxsqlen^2。
可以通过下面的图来理解该工作原理:
(1,3) 处的 2 表示到该索引为止有个边长为 2 的正方形。同样的,(1,2) 和 (2,2) 处的 2 也表示到该索引为止有边长为 2 的正方形。到了 (3,3),原始矩阵中 (3,3) 中的 1,形成了边长为 3 的正方形,所以在 (3,3)中应该为 3。
现在考虑索引 (3,4)的情况,到 (3,4) 所能形成的最大正方形为 2,所以 (3,4) 应为 2。
复杂度分析
- 时间复杂度:O(mn)
- 空间复杂度:O(mn),用了一个大小相同的矩阵 dp。
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.size() == 0) {
return 0;
}
vector<vector<int>> dp(matrix.size()+1, vector<int>(0, matrix[0].size()+1));
int max_len = 0;
for (int i = 1; i <= matrix.size(); ++i) {
for (int j = 1; j <= matrix[i-1].size(); ++j) {
if (matrix[i-1][j-1] == '1') {
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]);
dp[i][j] = min(dp[i][j], dp[i][j-1]);
max_len = max(max_len, dp[i][j]);
}
}
}
return max_len * max_len;
}
};
理解 min(上, 左, 左上) + 1
如题,动态规划方法的题解中,都会涉及到下列形式的代码:
if (grid(i, j) == 1) {
dp(i, j) = min(dp(i-1, j), dp(i, j-1), dp(i-1, j-1)) + 1;
}
翻译成中文
若某格子值为 1 ,则以此为右下角的正方形的、最大边长为:上面的正方形、左面的正方形或左上的正方形中,最小的那个,再加上此格。
先来阐述简单共识
- 若形成正方形(非单 1),以当前为右下角的视角看,则需要:当前格、上、左、左上都是 1
- 可以换个角度:当前格、上、左、左上都不能受 0 的限制,才能成为正方形
上面详解了 三者取最小 的含义:
- 图1:受限于左上的0
- 图2:受限于上边的0
- 图3:受限于左边的0
- 数字表示:以此为正方形右下角的最大边长
- 黄色表示:格子 ? 作为右下角的正方形区域
就像 木桶的短板理论 那样——附近的最小边长,才与 ? 的最长边长有关。
此时已可得到递推公式 if (grid[i][j] == 1) f[i][j] = min(f[i-1][j-1], f[i-1][j], f[i][j-1]) + 1;