LeetCode 1637.两点之间不包含任何点的最宽垂直区域

2024-02-25 07:28

本文主要是介绍LeetCode 1637.两点之间不包含任何点的最宽垂直区域,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

给你 n 个二维平面上的点 points ,其中 points[i] = [xi, yi] ,请你返回两点之间内部不包含任何点的 最宽垂直区域 的宽度。

垂直区域 的定义是固定宽度,而 y 轴上无限延伸的一块区域(也就是高度为无穷大)。 最宽垂直区域 为宽度最大的一个垂直区域。

请注意,垂直区域 边上 的点 不在 区域内。

示例 1:
在这里插入图片描述


输入:points = [[8,7],[9,9],[7,4],[9,7]]
输出:1
解释:红色区域和蓝色区域都是最优区域。
示例 2:

输入:points = [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]]
输出:3

提示:

n == points.length
2 <= n <= 105
points[i].length == 2
0 <= xi, yi <= 109

法一:排序后遍历一遍即可:

class Solution {
public:int maxWidthOfVerticalArea(vector<vector<int>>& points) {sort(points.begin(), points.end(), [] (vector<int> left, vector<int> right) {return left[0] < right[0];});int ans = points[1][0] - points[0][0];for (int i = 2; i < points.size(); ++i){if (points[i][0] - points[i - 1][0] > ans){ans = points[i][0] - points[i - 1][0];}}return ans;}
};

如果points的长度为n,此算法时间复杂度为O(nlogn),空间复杂度为O(1)。

法二:将法一中的sort替换为自己写的快排:

class Solution {
public:int maxWidthOfVerticalArea(vector<vector<int>>& points) {quickQort(points, 0, points.size() - 1);int ans = points[1][0] - points[0][0];for (int i = 2; i < points.size(); ++i){if (points[i][0] - points[i - 1][0] > ans){ans = points[i][0] - points[i - 1][0];}}return ans;}private:void quickQort(vector<vector<int>>& points, int begin, int end){if (begin >= end){return;}int divider = begin - 1;for (int i = begin; i <= end - 1; ++i){if (points[i][0] < points[end][0]){++divider;swap(points[i], points[divider]);}}swap(points[divider + 1], points[end]);quickQort(points, begin, divider);quickQort(points, divider + 2, end);}
};

如果points的长度为n,此算法时间复杂度为O(nlogn),空间复杂度为O(1)。

这篇关于LeetCode 1637.两点之间不包含任何点的最宽垂直区域的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/744785

相关文章

Javaee多线程之进程和线程之间的区别和联系(最新整理)

《Javaee多线程之进程和线程之间的区别和联系(最新整理)》进程是资源分配单位,线程是调度执行单位,共享资源更高效,创建线程五种方式:继承Thread、Runnable接口、匿名类、lambda,r... 目录进程和线程进程线程进程和线程的区别创建线程的五种写法继承Thread,重写run实现Runnab

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

深度解析Java项目中包和包之间的联系

《深度解析Java项目中包和包之间的联系》文章浏览阅读850次,点赞13次,收藏8次。本文详细介绍了Java分层架构中的几个关键包:DTO、Controller、Service和Mapper。_jav... 目录前言一、各大包1.DTO1.1、DTO的核心用途1.2. DTO与实体类(Entity)的区别1

java Long 与long之间的转换流程

《javaLong与long之间的转换流程》Long类提供了一些方法,用于在long和其他数据类型(如String)之间进行转换,本文将详细介绍如何在Java中实现Long和long之间的转换,感... 目录概述流程步骤1:将long转换为Long对象步骤2:将Longhttp://www.cppcns.c

Java内存区域与内存溢出异常的详细探讨

《Java内存区域与内存溢出异常的详细探讨》:本文主要介绍Java内存区域与内存溢出异常的相关资料,分析异常原因并提供解决策略,如参数调整、代码优化等,帮助开发者排查内存问题,需要的朋友可以参考下... 目录一、引言二、Java 运行时数据区域(一)程序计数器(二)Java 虚拟机栈(三)本地方法栈(四)J

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim

golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法

《golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法》:本文主要介绍golang获取当前时间、时间戳和时间字符串及它们之间的相互转换,本文通过实例代码给大家介绍的非常详细,感兴趣... 目录1、获取当前时间2、获取当前时间戳3、获取当前时间的字符串格式4、它们之间的相互转化上篇文章给大家介

Vue中组件之间传值的六种方式(完整版)

《Vue中组件之间传值的六种方式(完整版)》组件是vue.js最强大的功能之一,而组件实例的作用域是相互独立的,这就意味着不同组件之间的数据无法相互引用,针对不同的使用场景,如何选择行之有效的通信方式... 目录前言方法一、props/$emit1.父组件向子组件传值2.子组件向父组件传值(通过事件形式)方

Python实现PDF与多种图片格式之间互转(PNG, JPG, BMP, EMF, SVG)

《Python实现PDF与多种图片格式之间互转(PNG,JPG,BMP,EMF,SVG)》PDF和图片是我们日常生活和工作中常用的文件格式,有时候,我们可能需要将PDF和图片进行格式互转来满足... 目录一、介绍二、安装python库三、Python实现多种图片格式转PDF1、单张图片转换为PDF2、多张图

Java对象和JSON字符串之间的转换方法(全网最清晰)

《Java对象和JSON字符串之间的转换方法(全网最清晰)》:本文主要介绍如何在Java中使用Jackson库将对象转换为JSON字符串,并提供了一个简单的工具类示例,该工具类支持基本的转换功能,... 目录前言1. 引入 Jackson 依赖2. 创建 jsON 工具类3. 使用示例转换 Java 对象为