leetcode221 最大正方形

拼搏现实的明天。 2023-06-17 04:58 12阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70][]

在一个由 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)` 表示的是必须以ij为右下角，由 1 组成的最大正方形的边长

![20191127160229979.png][]

注：由于dp数组横竖我给长度加了1，导致判断matrix时是i-1和j-1

public class Solution {
        public int maximalSquare(char[][] matrix) {
            int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
            int[][] dp = new int[rows + 1][cols + 1];
            int maxsqlen = 0;
            for (int i = 1; i <= rows; i++) {
                for (int j = 1; j <= cols; j++) {
                    if (matrix[i-1][j-1] == '1'){
                        dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
                        maxsqlen = Math.max(maxsqlen, dp[i][j]);
                    }
                }
            }
            return maxsqlen * maxsqlen;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2019112716003369.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ=,size_16,color_FFFFFF,t_70
[20191127160229979.png]: https://img-blog.csdnimg.cn/20191127160229979.png

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode-221. 最大正方形

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

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

相关 221. 最大正方形

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

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

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

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

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

相关 leetcode221 最大正方形

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nk

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

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

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

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

相关 221. 最大正方形

题目： [221. 最大正方形][221.] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_te

爱被打了一巴掌/ 2023年03月04日 14:28/ 0 赞/ 35 阅读

相关 221最大正方形

一、前言标签：动态规划、栈运用、双指针。问题来源LeetCode 5 难度：中等。问题链接：[https://leetcode-cn.com/problems/

深藏阁楼爱情的钟/ 2023年02月28日 15:26/ 0 赞/ 17 阅读

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

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

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

相关 LeetCode-221. 最大正方形

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

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

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