专栏首页刷题笔记【LeetCode】221. 最大正方形

【LeetCode】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

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximal-square

动态规划 二维数组可以降低到一维存储。

一开始就没分析对,但是蒙对了几个测试样例,所以怎么改都不对。

不是 比较 前 中 后 是比较 前 中 和更新前的 前

class Solution {
    int Min(int a,int b){
        if(a<b){return a;}
        return b;
    }
    int Max(int a,int b){
        if(a>b){return a;}
        return b;
    }
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.size()==0){return 0;}
        int maxans=0;
        int pre=0;
        vector<int>num(matrix[0].size());
        for(int a=0; a<matrix.size();a++){
            pre=0;
            for(int b=0;b<matrix[0].size();b++){
                int t=num[b];
                if(matrix[a][b]=='1'){
                    num[b]=Min(pre,num[b]);
                    if(b>0)num[b]=Min(num[b-1],num[b]);
                    num[b]++;
                    maxans=Max(maxans,num[b]);
                }else num[b]=0;
                pre=t;
            }
        }return maxans*maxans;
    }
};

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【LeetCode第 162 场周赛】回顾

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 【LeetCode】面试题46. 把数字翻译成字符串

    给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有...

    韩旭051
  • 【未完成】7-8 最长有效括号串 (20 分)13分

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • LWC 61:738. Monotone Increasing Digits

    LWC 61:738. Monotone Increasing Digits 传送门:738. Monotone Increasing Digits Probl...

    用户1147447
  • Unique Paths

    问题:从起点到终点总共有多少条路径 分析:f[x,y]=f[x+1,y]+f[x,y+1],用记忆化搜索就可以解决了 class Solution { publ...

    用户1624346
  • 用递归解决猴子吃桃问题

    用户7727433
  • leetcode-367-Valid Perfect Square

    chenjx85
  • 1021 个位数统计 (15 分)

    给定一个 k 位整数 N=dk−110k−1+⋯+d1101+d0 (0≤di≤9, i=0,⋯,k−1, dk−1>0),请编写程序统计每种不同的个位数字出现...

    可爱见见
  • hust Dating With Girls

    http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=573#problem/B 题意:求最大权...

    用户1624346
  • 剑指offer(61-67)题解

    例如,我们可以把一个只有根节点为1的二叉树序列化为"1,",然后通过自己的函数来解析回这个二叉树

    萌萌哒的瓤瓤

扫码关注云+社区

领取腾讯云代金券