LeetCode-221. 最大正方形

墨蓝 2022-01-27 01:23 185阅读 0赞

# [221. 最大正方形][221.] #

在一个由 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[i][j] = 1 + min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j])`  
dp\[i\]\[j\]表示以(i,j)为右下角所能构成的最大正方形的边长。

class Solution { 
    public:
        int maximalSquare(vector<vector<char>>& matrix) { 
            int len = matrix.size();
            if(len == 0) return 0;
            int width = matrix[0].size();
            vector<vector<int>> dp(len + 1,vector<int>(width + 1,0));
            int ans = 0;
            for(int i = 1;i <= len;i++) { 
                for(int j = 1;j <= width;j++) { 
                    if(matrix[i - 1][j - 1] == '1') { 
                        dp[i][j] = min(dp[i - 1][j - 1],min(dp[i - 1][j],dp[i][j - 1])) + 1;
                        ans = max(ans,dp[i][j]);
                    }
                }
            }   
            return ans*ans;
        }
    };

[221.]: https://leetcode-cn.com/problems/maximal-square/

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode-221. 最大正方形

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

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

相关 221. 最大正方形（JS实现）

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

╰+哭是因爲堅強的太久メ/ 2022年11月25日 13:22/ 0 赞/ 118 阅读

相关 leetcode 221. Maximal Square | 221. 最大正方形（优化的暴力解法+动态规划解法）

题目 [https://leetcode.com/problems/maximal-square/][https_leetcode.com_problems_maxima

蔚落/ 2022年10月07日 12:57/ 0 赞/ 123 阅读

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

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

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

相关 leetcode 221. Maximal Square 最大正方形面积 + 动态规划DP实现

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

淩亂°似流年/ 2022年06月08日 11:55/ 0 赞/ 146 阅读

相关 LeetCode:221. Maximal Square（数组中最大的正方形）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

分手后的思念是犯贱/ 2022年04月03日 09:10/ 0 赞/ 150 阅读

相关 LeetCode-221. 最大正方形

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

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

相关 leetcode221

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

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

相关【面试刷题-力扣经典】动规：221. 最大正方形

【题目】在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。输入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1

红太狼/ 2021年09月21日 06:04/ 0 赞/ 252 阅读

相关 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 赞/ 360 阅读