Leetcode 3382. Maximum Area Rectangle With Point Constraints II
- Leetcode 3382. Maximum Area Rectangle With Point Constraints II
- 1. 解题思路
- 2. 代码实现
- 题目链接:3382. Maximum Area Rectangle With Point Constraints II
1. 解题思路
这一题是题目3380. Maximum Area Rectangle With Point Constraints I的进阶版,两者内容上是完全相同的,但是要求的时间复杂度上面天差地别,前者还可以使用暴力循环的方式在 O ( N 2 ) O(N^2) O(N2)的时间复杂度当中完成,而后者就完全不行了,必须对其进行优化。
而这里的优化方法则是使用了分段树(Segment Tree),关于分段树的相关内容网上已经有非常多的介绍了,我自己也整理过一个小文章来做备忘(经典算法:Segment Tree),因此这里就不做过多的展开了,有兴趣的读者可以移步去了解一下相关的内容。
我们就直接介绍一下这里的核心思路吧,我的思路的话就是首先将所有的点按照 ( x , y ) (x, y) (x,y)进行有序排列,然后,我们顺序考察每一个点作为右侧上顶点的情况,此时,之前的所有点显然 x x x坐标均不大于当前点的 x x x坐标,因此,我们只需要考察是否在其前方能够找到3个点,使之构成一个满足条件的矩形,然后更新我们的最大面积即可。
要满足题目条件,事实上,我们就是要满足下述条件:
- 显然,其前一个点必须与当前点的 x x x坐标相同,作为矩形的右下顶点;
- 当前顶点(右上顶点)与前一点(右下顶点)所处两处的 y y y坐标上之前最近的点均存在且对应的 x x x坐标相同
- 在上述4个顶点所组成的矩阵当中,不存在其他的点,即对应的 y y y区间之中,所有点的 x x x坐标均需要小于2中给出的左边界上两个点的 x x x坐标。
可以看到,对于第三点,事实上就是要求范围内的最大值,因此就可以完美使用segment tree来进行实现了。
2. 代码实现
给出python代码实现:
class SegmentTree:def __init__(self, arr):self.length = len(arr)self.tree = self.build(arr)def feature_func(self, *args):return max(args)def build(self, arr):n = len(arr)tree = [0 for _ in range(2*n)]for i in range(n):tree[i+n] = arr[i]for i in range(n-1, 0, -1):tree[i] = self.feature_func(tree[i<<1], tree[(i<<1) | 1])return treedef update(self, idx, val):idx = idx + self.lengthself.tree[idx] = valwhile idx > 1:self.tree[idx>>1] = self.feature_func(self.tree[idx], self.tree[idx ^ 1])idx = idx>>1returndef query_range(self, lb, rb):lb += self.length rb += self.lengthnodes = []while lb < rb:if lb & 1 == 1:nodes.append(self.tree[lb])lb += 1if rb & 1 == 0:nodes.append(self.tree[rb])rb -= 1lb = lb >> 1rb = rb >> 1if lb == rb:nodes.append(self.tree[rb])return self.feature_func(*nodes)def query(self, idx):return self.tree[idx + self.length]class Solution:def maxRectangleArea(self, xCoord: List[int], yCoord: List[int]) -> int:points = [(x, y) for x, y in zip(xCoord, yCoord)]n = len(points)points = sorted(points)cols = sorted(set(yCoord))closest = SegmentTree([-1 for _ in cols])ans = -1for i in range(n-1):y1_idx = bisect.bisect_left(cols, points[i][1])if points[i][0] == points[i+1][0]:y2_idx = bisect.bisect_left(cols, points[i+1][1])x1 = closest.query(y1_idx)x2 = closest.query(y2_idx)if x1 != -1 and x2 != -1 and x1 == x2:S = (points[i+1][1] - points[i][1]) * (points[i][0] - x1)if S >= ans and (y2_idx - y1_idx <= 1 or closest.query_range(y1_idx+1, y2_idx-1) < x1):ans = max(ans, S)closest.update(y1_idx, points[i][0])return ans
提交代码评测得到:耗时3270ms,占用内存67.6MB。
相关文章:
Leetcode 3382. Maximum Area Rectangle With Point Constraints II
Leetcode 3382. Maximum Area Rectangle With Point Constraints II 1. 解题思路2. 代码实现 题目链接:3382. Maximum Area Rectangle With Point Constraints II 1. 解题思路 这一题是题目3380. Maximum Area Rectangle With Point Constraints I的进阶版&#…...
MitelMiCollab 身份绕过导致任意文件读取漏洞复现(CVE-2024-41713)
0x01 产品描述: Mitel MiCollab 是一个企业协作平台,它将各种通信工具整合到一个应用程序中,提供语音和视频通话、消息传递、状态信息、音频会议、移动支持和团队协作功能。0x02 漏洞描述: Mitel MiCollab 的 NuPoint 统一消息 (NPM) 组件中存在身份验证绕过漏洞,由于输入…...
DVWA 靶场 SQL 注入报错 Illegal mix of collations for operation ‘UNION‘ 的解决方案
在 dvwa 靶场进行联合 SQL 注入时,遇到报错 Illegal mix of collations for operation UNION报错如下图: 解决办法: 找到文件MySQL.php 大致位置在dvwaincludesDBMS 目录下 使用编辑器打开 检索$create_db 第一个就是 在{$_DVWA[ ‘db_d…...
京准电钟分享:医院网络内NTP时间同步服务器作用是什么?
京准电钟分享:医院网络内NTP时间同步服务器作用是什么? 京准电钟分享:医院网络内NTP时间同步服务器作用是什么? 时间同步技术必定将是整个大数据处理系统的重要支撑和保障。时间同步技术使数据产生与处理系统的所有节点具有全局…...
HTML DOM API
HTMLInputElement HTMLInputElement 接口提供了特定的属性和方法,用于管理 <input> 元素的选项、布局和外观。 HTMLInputElement 和 <input> 之间的关系可以理解为接口与具体元素的关系: <input> 元素: <input> 是…...
java时间处理SimpleDateFormat详解
文章目录 常用构造函数日期格式模式常见用法1. 格式化日期2. 解析日期字符串 注意事项示例扩展:指定区域和时区 SimpleDateFormat 是 Java 中用于日期和时间格式化的类,属于 java.text 包。它允许开发者将日期对象格式化为字符串,或者将字符…...
redis-stack redisSearch环境安装搭建
RedisSearch在redis许可证变更之后显得是redis中的一大特色,闲来无事学习记录一下。 尝试通过源码编译redisSearch,貌似非常费劲,所以建议使用docker或者Linux的发行包进行安装redis-stack。redis-stack是基于redis的模块化机制进行一个扩展…...
go返回多个errors
起因 有时候大家可能需要返回多个errors的场景,所以这个时候可能就会考虑如何实现、怎么实现比较好 实现 package mainimport ("errors""fmt" )func main() {errs : retErrors("hello,world")fmt.Println(errs) }func retErrors(t…...
Monkey结合appium模拟操作特定界面
目录 1. 使用 Monkey 操作特定界面(通过UI标识来限制) 2. 结合 uiautomator 或 appium 定位特定元素 步骤: 3. 使用 Monkey Appium 控制特定界面点击 4. 如何结合 Appium 与 Monkey 5. 限制 Monkey 只点击固定界面上的元素 使用 --pc…...
Ubuntu22.04深度学习环境安装【cuda+cudnn】
为了复现一篇深度学习论文,特意安装了Linux系统。前一天已经安装Linux显卡驱动,现在需要安装cuda、cudnn等。 论文代码 论文PDF 确定包版本: 根据论文提供的代码。在requirements.txt中发现cuda版本为11.7,cudnn为8.5.0,python没…...
go语言的sdk项目搭建与git 操作标签tag并推送至远程仓库
在搭建 SDK 项目并结合 Git 操作标签(Tag)时,通常会涉及项目初始化、版本管理、Git 标签的创建与管理等内容。以下是一个完整的步骤指南,帮助您搭建 SDK 项目并学习如何使用 Git 标签。 ### 1. **搭建 SDK 项目** 首先ÿ…...
从零用java实现 小红书 springboot vue uniapp (1)
前言 偶尔会用小红书发一些笔记 闲来无事 想自己实现一个小红书 正好可以学习一下 帖子 留言 im 好友 推送 等功能 下面我们就从零 开发一个小红书 后台依旧用我们的会员系统的脚手架 演示 http://120.26.95.195:8889/ 客户端我们使用uniapp 我们首先对主页进行一个分解 顶部我…...
Python爬虫——HTML中Xpath定位
Xpath是一种路径查询语言。利用一个路径表达式从html文档中找到我们需要的数据位置,进而将其写入到本地或者数据库中。 学习Xpath爬虫,我们首先学习一下python中lxml库 关于库 lxml 终端下载Xpath需要用到的模块 pip install lxml 关于HTML 超文本标…...
电脑无法识别usb设备怎么办?电脑无法识别usb解决方法
usb设备是我们常解除的外部操作以及存储设备,它可以方便用户数据传输以及操作输入。但在使用过程中,大家基本都碰到过电脑无法识别usb设备这种情况。这种情况下,我们应该怎么办呢?下面将为你介绍几种可能的原因和解决方法…...
思特奇政·企数智化产品服务平台正式发布,助力运营商政企数智能力跃迁
数字浪潮下,产业数字化进程加速发展,信息服务迎来更广阔的天地,同时也为运营商政企支撑系统提出了更高要求。12月4日,2024数字科技生态大会期间,思特奇正式发布政企数智化产品服务平台,融合应用大数据、AI等新质生产要素,构建集平台服务、精准营销、全周期运营支撑、智慧大脑于…...
【Springboot3+vue3】从零到一搭建Springboot3+vue3前后端分离项目之前端环境搭建
【Springboot3vue3】从零到一搭建Springboot3vue3前后端分离项目之前端环境搭建 2 前端环境搭建2.1 环境准备2.2 创建Vue3项目2.3 项目搭建准备2.4 安装Element Plus2.5 安装axios2.5.1 配置(创建实例,配置请求,响应拦截器)2.5.2 …...
手写Mybatis框架源码(简写)
pom文件: springboot版本:2.6.5 jdk:8 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance&q…...
Flask返回中文Unicode编码(乱码)解决方案
大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…...
最大值和最小值的差
最大值和最小值的差 C语言代码C 语言代码Java语言代码Python语言代码 💐The Begin💐点点关注,收藏不迷路💐 输出一个整数序列中最大的数和最小的数的差。 输入 第一行为M,表示整数个数,整数个数不会大于1…...
如何在 IntelliJ IDEA 中为 Spring Boot 应用实现热部署
文章目录 1. 引言2. 准备工作3. 添加必要的依赖4. 配置 IntelliJ IDEA4.1 启用自动编译4.2 开启热部署策略 5. 测试热部署6. 高级技巧7. 注意事项8. 总结 随着现代开发工具的进步,开发者们越来越重视提高生产力的特性。对于 Java 开发者来说,能够在不重启…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
springboot 百货中心供应链管理系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,百货中心供应链管理系统被用户普遍使用,为方…...
关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
倒装芯片凸点成型工艺
UBM(Under Bump Metallization)与Bump(焊球)形成工艺流程。我们可以将整张流程图分为三大阶段来理解: 🔧 一、UBM(Under Bump Metallization)工艺流程(黄色区域ÿ…...
react菜单,动态绑定点击事件,菜单分离出去单独的js文件,Ant框架
1、菜单文件treeTop.js // 顶部菜单 import { AppstoreOutlined, SettingOutlined } from ant-design/icons; // 定义菜单项数据 const treeTop [{label: Docker管理,key: 1,icon: <AppstoreOutlined />,url:"/docker/index"},{label: 权限管理,key: 2,icon:…...
