leetcode221

小鱼儿 2021-12-19 04:11 234阅读 0赞

int maximalSquare(vector<vector<char>>& matrix) {
            int height=matrix.size();
            if(height==0)
                return 0;
            int width=matrix[0].size();
            vector<vector<int>>  vec(height,vector<int>(width,0));
            int result=0;
            for(int i=0;i<height;i++)
            {
                for(int j=0;j<width;j++)
                {
                    if(matrix[i][j]=='1')
                    {
                        vec[i][j]=1;
                        if(i>0&&j>0)
                            vec[i][j]+=min(min(vec[i-1][j],vec[i][j-1]),vec[i-1][j-1]);
                    }
                    result=max(result,vec[i][j]);
                }
            }
            return result*result;
            
        }

本题是动态规划的题目，vec\[i,j\]记录的是以matrix\[i,j\]为右下角的所能构成的正方形区域的边长最大值。

递推公式，vec\[i\]\[j\]+=min(min(vec\[i-1\]\[j\],vec\[i\]\[j-1\]),vec\[i-1\]\[j-1\])，计算的是当前单元格的“左”、“上”、“左上”三个单元格的最小值，再+1。

转载于:https://www.cnblogs.com/asenyang/p/9787674.html

发表评论取消回复

表情：

评论列表（有 0 条评论，234人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-221. 最大正方形

目录题目思路动态规划动态规划(优化) 题目来源 [221. 最大正方形][221.] 题目思路现在我们

一时失言乱红尘/ 2024年03月23日 10:06/ 0 赞/ 123 阅读

相关 LeetCode_动态规划_中等_221.最大正方形

目录 1.题目 2.思路 3.代码实现（Java） 1.题目在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，

男娘i/ 2023年10月06日 22:44/ 0 赞/ 41 阅读

相关 leetcode221 最大正方形

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nk

拼搏现实的明天。/ 2023年06月17日 04:58/ 0 赞/ 29 阅读

相关 LeetCode 221.最大正方形解法

/ LeetCode 221.最大正方形形成22的小正方形，基础上 [ [a, b] [c, d(?)] ]

悠悠/ 2023年03月13日 01:57/ 0 赞/ 43 阅读

相关 LeetCode 221场周赛题解

【GiantPandaCV导语】这是LeetCode的第221场周赛的题解，本期考察的知识点有模拟，贪心，优先队列，01Trie树等。比赛链接 https://

￡神魔★判官ぃ/ 2023年01月01日 13:53/ 0 赞/ 137 阅读

相关 Leetcode 221 最大正方形(DP)

题目重述在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。示例 1： ![在这里插入图片描述][watermark

墨蓝/ 2022年08月29日 14:54/ 0 赞/ 168 阅读

相关 leetcode 221. Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all

男娘i/ 2022年08月20日 14:28/ 0 赞/ 50 阅读

相关 LeetCode-221. 最大正方形

[221. 最大正方形][221.] 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。示例: 输入: 1 0 1 0

墨蓝/ 2022年01月27日 01:23/ 0 赞/ 245 阅读

相关 leetcode221

int maximalSquare(vector<vector<char>>& matrix) { int height=matrix.size

小鱼儿/ 2021年12月19日 04:11/ 0 赞/ 235 阅读

相关 LeetCode : 221. Maximal Square 最大正方形

试题 Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containin

た入场券/ 2021年06月24日 16:11/ 0 赞/ 463 阅读