【1139. 最大的以 1 为边界的正方形】
来源:力扣(LeetCode)
描述:
给你一个由若干 0 和 1 组成的二维网格 grid
,请你找出边界全部由 1 组成的最大 正方形 子网格,并返回该子网格中的元素数量。如果不存在,则返回 0。
示例 1:
输入:grid = [[1,1,1],[1,0,1],[1,1,1]]
输出:9
示例 2:
输入:grid = [[1,1,0,0]]
输出:1
提示:
- 1 <= grid.length <= 100
- 1 <= grid[0].length <= 100
- grid[i][j] 为 0 或 1
方法:动态规划
思路与算法
我们假设以 (x, y) 为右下方顶点的最大的正方形边长为 l,此时正方形的四个顶点分别为 (x − l + 1, y − l + 1), (x, y − l + 1), (x − l + 1, y), (x, y),此时需要保证正方形的四条边上的数字均为 1。我们设 left[x][y] 表示以 (x, y) 为起点左侧连续 1 的最大数目,right[x][y] 表示以 (x, y) 为起点右侧连续 1 的最大数目,up[x][y] 表示从 (x, y) 为起点上方连续 1 的最大数目,down[x][y] 表示以 (x, y) 为起点下方连续 1 的最大数目。此时正方形的四条边中以四个顶点为起点的连续 1 的数目分别为:上侧边中以 (x − l + 1, y − l + 1) 为起点连续 1 数目为 right[x − l + 1][y − l + 1],左侧边中以 (x − l + 1, y − l + 1) 为起点连续 1 的数目为 down[x − l + 1][y − l + 1],右侧边中以 (x, y) 为起点连续 1 的数目为 up[x][y],下侧边中以 (x,y) 为起点连续 1 的数目为 left[x][y]。
如果连续 1 的数目大于等于 l,则构成一条「合法」的边,如果正方形的四条边均「合法」,此时一定可以构成边界全为 1 且边长为 l 的正方形。
我们只需要求出以 (x, y) 为起点四个方向上连续 1 的数目,枚举边长 l 即可求出以 (x, y) 为右下顶点构成的边界为 1 的最大正方形,此时我们可以求出矩阵中边界为 1 的最大正方形。
本题即转换为求矩阵中任意位置 (x, y) 为起点上下左右四个方向连续 1 的最大数目,此时可以利用动态规划:
-
如果当前 grid[x][x] = 0 此时,四个方向的连续 1 的长度均为 0;
-
如果当前 grid[x][x] = 1 此时,四个方向的连续 1 的最大数目分别等于四个方向上前一个位置的最大数目加 1,计算公式如下:
在实际计算过程中我们可以进行优化,不必全部计算出四个方向上的最大连续 1 的数目,可以进行如下优化:
只需要求出每个位置 (x, y) 为起点左侧连续 1 的最大数目 left[x][y] 与上方连续 1 的最大数目 up[x][y] 即可。假设当前正方形的边长为 l,此时只需检测 up[x][y], left[x][y], left[x − l + 1][y], up[x][y − l + 1] 是否均满足大于等于 l 即可检测正方形的合法性。
枚举正方形的边长时可以从大到小进行枚举,我们已经知道以 (x, y) 为起点左侧连续 1 的最大数目 left[x][y] 与上方连续 1 的最大数目 up[x][y],此时能够成正方形的边长的最大值一定不会超过二者中的最小值 min(left[x][y], up[x][y]),从大到小枚举直到可以构成“合法”的正方形即可。
代码:
class Solution {
public:int largest1BorderedSquare(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();vector<vector<int>> left(m + 1, vector<int>(n + 1));vector<vector<int>> up(m + 1, vector<int>(n + 1));int maxBorder = 0;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (grid[i - 1][j - 1] == 1) {left[i][j] = left[i][j - 1] + 1;up[i][j] = up[i - 1][j] + 1;int border = min(left[i][j], up[i][j]);while (left[i - border + 1][j] < border || up[i][j - border + 1] < border) {border--;}maxBorder = max(maxBorder, border);}}}return maxBorder * maxBorder;}
};
执行用时:8 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗:11.4 MB, 在所有 C++ 提交中击败了54.29%的用户
复杂度分析
时间复杂度:O(m × n × min(m, n)),其中 m 表示矩阵的行数,n 表示矩阵的列数。
空间复杂度:O(m × n),其中 m 表示矩阵的行数,n 表示矩阵的列数。需要保存矩阵中每个位置的最长连续 1 的数目,需要的空间为 O(m × n)。
author:LeetCode-Solution
相关文章:

【1139. 最大的以 1 为边界的正方形】
来源:力扣(LeetCode) 描述: 给你一个由若干 0 和 1 组成的二维网格 grid,请你找出边界全部由 1 组成的最大 正方形 子网格,并返回该子网格中的元素数量。如果不存在,则返回 0。 示例 1&#…...

windows11安装sqlserver2022报错
window11安装SQL Server 2022 报错 糟糕… 无法安装SQL Server (setup.exe)。此 SQL Server安装程序介质不支持此OS的语言,或没有SQL Server英语版本的安装文件。请使用匹配的特定语言SQL Server介质;或安装两个特定语言MUI,然后通过控制面板的区域设置…...

Python快速上手系列--日志模块--详解篇
前言本篇主要说说日志模块,在写自动化测试框架的时候我们就需要用到这个模块了,方便我们快速的定位错误,了解软件的运行情况,更加顺畅的调试程序。为什么要用到日志模块,直接print不就好了!那得写多少print…...

【THREE.JS学习(1)】绘制一个可以旋转、放缩的立方体
学习新技能,做一下笔记。在使用ThreeJS的时候,首先创建一个场景const scene new THREE.Scene();接着,创建一个相机其中,THREE.PerspectiveCamera()四个参数分别为:1.fov 相机视锥体竖直方向视野…...

数仓实战 - 滴滴出行
项目大致流程: 1、项目业务背景 1.1 目的 本案例将某出行打车的日志数据来进行数据分析,例如:我们需要统计某一天订单量是多少、预约订单与非预约订单的占比是多少、不同时段订单占比等 数据海量 – 大数据 hive比MySQL慢很多 1.2 项目架…...

python虚拟环境与环境变量
一、环境变量 1.环境变量 在命令行下,使用可执行文件,需要来到可执行文件的路径下执行 如果在任意路径下执行可执行文件,能够有响应,就需要在环境变量配置 2.设置环境变量 用户变量:当前用户登录到系统,…...
BeautifulSoup文档4-详细方法 | 用什么方法对文档树进行搜索?
4-详细方法 | 用什么方法对文档树进行搜索?1 过滤器1.1 字符串1.2 正则表达式1.3 列表1.4 True1.5 可以自定义方法2 find_all()2.1 参数原型2.2 name参数2.3 keyword 参数2.4 string 参数2.5 limit 参数2.6 recursive 参数3 find()4 find_parents()和find_parent()5…...
初识Tkinter界面设计
目录 前言 一、初识Tkinter 二、Label控件 三、Button控件 四、Entry控件 前言 本文简单介绍如何使用Python创建一个界面。 一、初识Tk...

软件测试面试题中的sql题目你会做吗?
目录 1.学生表 2.一道SQL语句面试题,关于group by表内容: 3.表中有A B C三列,用SQL语句实现:当A列大于B列时选择A列否则选择B列,当B列大于C列时选择B列否则选择C列 4. 5.姓名:name 课程:subject 分数&…...

VS实用调试技巧
一.什么是BUG🐛Bug一词的原意是虫子,而在电脑系统或程序中隐藏着的一些未被发现的缺陷或问题,人们也叫它"bug"。这是为什么呢?这就要追溯到一个程序员与飞蛾的故事了。Bug的创始人格蕾丝赫柏(Grace Murray H…...

通俗易懂理解三次握手、四次挥手(TCP)
文章目录1、通俗语言理解1.1 三次握手1.2 四次挥手2、进一步理解三次握手和四次挥手2.1 三次握手2.2 四次挥手1、通俗语言理解 1.1 三次握手 C:客户端 S:服务器端 第一次握手: C:在吗?我要和你建立连接。 第二次握手ÿ…...

1.1 什么是并发
1.1 什么是并发 并发:指两个或更多独立的活动同时发生。并发在生活中随处可见。我们可以一边走路一边说话,也可以两只手同时做不同的动作。 1.1.1 计算机系统中的并发 当我们提到计算机术语的“并发”,指的是在单个系统里同时执行多个独立…...

万字讲解你写的代码是如何跑起来的?
今天我们来思考一个简单的问题,一个程序是如何在 Linux 上执行起来的? 我们就拿全宇宙最简单的 Hello World 程序来举例。 #include <stdio.h> int main() {printf("Hello, World!\n");return 0; } 我们在写完代码后,进行…...
034.Solidity入门——21不可变量
Solidity 中的不可变量是在编译时就被确定的常量,也称为常量变量(constant variable)或只读变量(read-only variable)。这些变量在定义时必须立即初始化,并且在整个合约中都无法被修改,可以在函…...

Vulnhub 渗透练习(四)—— Acid
环境搭建 环境下载 kail 和 靶机网络适配调成 Nat 模式,实在不行直接把网络适配还原默认值,再重试。 信息收集 主机扫描 没扫到,那可能端口很靠后,把所有端口全扫一遍。 发现 33447 端口。 扫描目录,没什么有用的…...
C++ 在线工具
online编译器https://godbolt.org/Online C Compiler - online editor (onlinegdb.com) https://www.onlinegdb.com/online_c_compilerC Shell (cpp.sh) https://cpp.sh/在线文档Open Standards (open-std.org)Index of /afs/cs.cmu.edu/academic/class/15211/spring.96/wwwC P…...

使用MMDetection进行目标检测、实例和全景分割
MMDetection 是一个基于 PyTorch 的目标检测开源工具箱,它是 OpenMMLab 项目的一部分。包含以下主要特性: 支持三个任务 目标检测(Object Detection)是指分类并定位图片中物体的任务实例分割(Instance Segmentation&a…...

使用ThreadLocal实现当前登录信息的存取
有志者,事竟成 文章持续更新,可以关注【小奇JAVA面试】第一时间阅读,回复【资料】获取福利,回复【项目】获取项目源码,回复【简历模板】获取简历模板,回复【学习路线图】获取学习路线图。 文章目录一、使用…...

高通平台开发系列讲解(Android篇)AudioTrack音频流数据传输
文章目录 一、音频流数据传输通道创建1.1、流程描述1.2、流程图解二、音频数据传输2.1、流程描述2.2、流程图解沉淀、分享、成长,让自己和他人都能有所收获!😄 📢本篇章主要图解AudioTrack音频流数据传输 。 一、音频流数据传输通道创建 1.1、流程描述 AudioTrack在set函…...

BUUCTF-firmware1
题目下载:下载 新题型,记录一下 题目给出了flag形式,md5{网址:端口},下载发现是一个.bin文件 二进制文件,其用途依系统或应用而定。一种文件格式binary的缩写。一个后缀名为".bin"的文件&#x…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...

STM32HAL库USART源代码解析及应用
STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...
Web中间件--tomcat学习
Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机,它可以执行Java字节码。Java虚拟机是Java平台的一部分,Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)
macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 🍺 最新版brew安装慢到怀疑人生?别怕,教你轻松起飞! 最近Homebrew更新至最新版,每次执行 brew 命令时都会自动从官方地址 https://formulae.…...