LeetCode : 221. Maximal Square 最大正方形

た入场券 2021-06-24 16:11 417阅读 0赞

**试题**  
Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

Example:

Input:

1 0 1 0 0  
1 0 1 1 1  
1 1 1 1 1  
1 0 0 1 0

Output: 4  
**代码**  
很好理解的动归。dp为以当前位置为最大正方形右下角角点的边长。dp\[i\]\[j\]主要有dp\[i\]-1\[j-1\]；dp\[i-1\]\[j\]； dp\[i\]\[j-1\] 三个长度限制。初始化方式注意一下。

class Solution {
        public int maximalSquare(char[][] matrix) {
            if(matrix==null || matrix.length==0 || matrix[0].length==0) return 0;
            int row = matrix.length, col = matrix[0].length;
            int[][] dp = new int[row+1][col+1];
            int max = 0;
            for(int i=1; i<=row; i++){
                for(int j=1; j<=col; j++){
                    if(matrix[i-1][j-1]=='1'){
                        dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
                        max = Math.max(dp[i][j], max);
                    }
                }
            }
            
            return max*max;
        }
    }

节省空间：

发表评论取消回复

表情：

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

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

相关阅读

相关 221. 最大正方形

打卡!!!每日一题今天继续给大家分享一道动态规划类型的题目，不过该题目的状态转移方程比较难以理解，我会详细的给大家分析一下题目描述： > 在一个由 ‘0’ 和 ‘1’

川长思鸟来/ 2023年10月11日 18:04/ 0 赞/ 1 阅读

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

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

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

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

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

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

相关 Maximal Square（C++最大正方形）

（1）动态规划 class Solution { public: int maximalSquare(vector<vector<cha

不念不忘少年蓝@/ 2022年09月04日 00:49/ 0 赞/ 179 阅读

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

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

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

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

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

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

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

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

相关 LeetCode-221. 最大正方形

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

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

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