LeetCode-221:最大正方形
程序员文章站
2022-07-13 21:59:31
...
一、题目描述
- 在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。
- 示例:
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4
二、解题思路
- 还是动态规划,这里我们可以定义一个二维数组
dp[][]
,dp[i][j]
用来表示以坐标为右下角的区域里存在的最大正方形边长。- 错误提示:不要让求正方形面积,就用
dp[i][j]
表示这个区域里最大正方形的面积。。。。。
- 错误提示:不要让求正方形面积,就用
-
dp[i][j]
的值不仅与dp[i - 1][j]
和dp[i][j - 1]
有关,还与dp[i - 1][j - 1]
有关,正方形的边长是由以上三者共同约束的。只有dp[i][j] == 1
时,才有可能存在正方形,且边长为三者最小值加1。否则 - 至此得到递推公式:,在时成立
- 边界条件:首行和首列的元素,跟随原矩阵即可,不用递推,即退化为只有1行1列的情况
- 在逐行遍历的过程中,有可能遇到0,从而使从一个大于零的数变回0,那么我们就需要一个变量来保存最大值。
二、解题代码
class Solution {
public:
int maximalSquare(vector<vector<char>> &matrix)
{
auto m = matrix.size();
if (!m)
return 0;
auto n = matrix[0].size();
if (!n)
return 0;
int dp[m][n];
int maxlen = 0, i, j;
for (i = 0; i < m; i++)
{
for (j = 0; j < n; j++)
{
if (matrix[i][j] == '1')
{
dp[i][j] = min(i > 0 && j > 0 ? dp[i - 1][j - 1] : 0, min(j > 0 ? dp[i][j - 1] : 0, i > 0 ? dp[i - 1][j] : 0)) + 1;
maxlen = max(maxlen, dp[i][j]);
}
else
{
dp[i][j] = 0;
}
}
}
return maxlen * maxlen;
}
};
图片的例子告诉我们不要用面积来求
上一篇: Prisma(二):基本概念及使用
下一篇: LeetCode-221.最大正方形