Leetcode 221. Maximal Square

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

For example, given the following matrix:

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

Return 4.

找出矩阵中最大的由1组成的正方形的大小。

dp[i][j]表示以这个点为右下角的最大正方形的边长。

如果一个点为0,那么这个点不能作为正方形的右下角,所以跳过.

一个点是否可以并入正方形取决于左边、上边、左上边格子的取值,取他们的最小值。

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int res = 0;
        for(int i = 0; i < matrix.size(); i ++)
        {
            for(int j = 0; j < matrix[0].size(); j ++)
            {
                if(matrix[i][j] == '0') 
                {
                    matrix[i][j] = 0;
                    continue;
                }
                int l = 0, u = 0, lu = 0;
                if(i != 0 && j != 0) lu = matrix[i - 1][j - 1];
                if(i != 0) l = matrix[i - 1][j];
                if(j != 0) u = matrix[i][j - 1];
                matrix[i][j] = 1 + min(min(l, u), lu);
                res = max(res, matrix[i][j] * matrix[i][j]);
            }
        }
        return res;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏闪电gogogo的专栏

Matplotlib

1622
来自专栏社区的朋友们

Kaggle实战:House Prices: Advanced Regression Techniques(下篇)

机器学习主要分为分类和回归两类。上一篇文章我们通过实例介绍了利用决策树和随机森林来做分类。 这次我们来预测房价,实际演练一下R语言中的回归分析模型。

3K2
来自专栏jojo的技术小屋

原 CSS3 filter

作者:汪娇娇 日期:2016.10.9 其实之前几乎都没用过filter属性,就算知道也只是在脑中留了点浅浅的印象,直到最近因为项目的原因,才对filter进行...

2073
来自专栏前端说吧

CSS3的transition动画功能

3296
来自专栏Android知识点总结

D4-Android绘图之和我一起画箭头

1312
来自专栏数据结构与算法

13:图像模糊处理

13:图像模糊处理 总时间限制: 1000ms 内存限制: 65536kB描述 给定n行m列的图像各像素点的灰度值,要求用如下方法对其进行模糊化处理: 1....

3815
来自专栏深度学习之tensorflow实战篇

R语言高级绘图命令(标题-颜色等)

plot(x)          以x的元素值为纵坐标、以序号为横坐标绘图 plot(x,y)        x(在x-轴上)与y(在y-轴上)的二元作图 ...

6576
来自专栏为数不多的Android技巧

Xfermode in android

Xfermode有三个实现类:AvoidXfermode, PixelXorXfermode以及PorterDuffXfermode。 前两个类因为不支持硬件加...

2064
来自专栏懒人开发

(10.5)James Stewart Calculus 5th Edition:Conic Sections

832
来自专栏一个小程序员的成长笔记

CSS深入理解学习笔记之z-index

1、z-index基础   z-index含义:指定了元素及其子元素的”z顺序“,而”z顺序“可以决定元素的覆盖顺序。z-index值越大越在上面。   z-i...

3095

扫码关注云+社区

领取腾讯云代金券