欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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]用来表示以坐标(i+1,j+1)(i+1,j+1)为右下角的区域里存在的最大正方形边长。
    • 错误提示:不要让求正方形面积,就用dp[i][j]表示这个区域里最大正方形的面积。。。。。
  • dp[i][j]的值不仅与dp[i - 1][j]dp[i][j - 1]有关,还与dp[i - 1][j - 1]有关,正方形的边长是由以上三者共同约束的。只有dp[i][j] == 1时,才有可能存在正方形,且边长为三者最小值加1。否则dp[i][j]=0dp[i][j] = 0
  • 至此得到递推公式:dp[i][j]=min(dp[i1][j],dp[i][j1],dp[i1][j1])+1dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1,在dp[i][j]==1dp[i][j] == 1时成立
  • 边界条件:首行和首列的元素,跟随原矩阵即可,不用递推,即退化为只有1行1列的情况
  • 在逐行遍历的过程中,有可能遇到0,从而使dp[i][j]dp[i][j]从一个大于零的数变回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;
    }
};

图片的例子告诉我们不要用面积来求
LeetCode-221:最大正方形