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

简介: 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 <= 10^5
  • points[i].length == 2
  • 0 <= xi, yi <= 10^9

解题思路

题目的意思其实就是要我们求距离最近的两个X坐标的距离。

具体实现过程如下:

  • 首先定义一个空数组 xList,用于存储所有点的 x 坐标。
  • 遍历二维数组 points,将每个点的 x 坐标加入数组 xList。
  • 对数组 xList 进行排序,以便计算任意两个点之间的 x 坐标差。
  • 定义一个变量 max,用于记录最大的 x 坐标差。初始值为 0。
  • 遍历排序后的数组 xList,从第二个元素开始计算当前元素与前一个元素之间的 x 坐标差,并将其与变量 max 中的值比较,取较大者更新 max 的值。
  • 返回变量 max 的值,即任意两个点之间的 x 坐标差的最大值。

AC代码

/**
 * @param {number[][]} points
 * @return {number}
 */
var maxWidthOfVerticalArea = function(points) {
    let xList = [];
    for(const point of points){
        xList.push(point[0]);
    }
    xList = xList.sort((a,b) => a-b);
    let max = 0;
    for(let i = 1; i < xList.length; i++){
        max = Math.max(max,xList[i] - xList[i - 1]);
    }
    return max;
};

公众号

关注公众号『前端也能这么有趣』,获取更多有趣内容。

说在后面

🎉 这里是 JYeontu,现在是一名前端工程师,有空会刷刷算法题,平时喜欢打羽毛球 🏸 ,平时也喜欢写些东西,既为自己记录 📋,也希望可以对大家有那么一丢丢的帮助,写的不好望多多谅解 🙇,写错的地方望指出,定会认真改进 😊,偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章,有兴趣的也可以关注下。在此谢谢大家的支持,我们下文再见 🙌。

目录
相关文章
|
9月前
|
数据可视化
R绘图 | 包含/比例关系环图
R绘图 | 包含/比例关系环图
83 0
|
17天前
单元格之间的距离
【6月更文挑战第17天】单元格之间的距离。
13 2
|
17天前
单元格内容与单元格边界之间的距离
【6月更文挑战第17天】单元格内容与单元格边界之间的距离。
12 1
|
2月前
|
JavaScript 前端开发 Java
根据地球上任意两点的经纬度计算两点间的距离
根据地球上任意两点的经纬度计算两点间的距离
50 2
|
2月前
ArcGIS矢量面要素中零碎小面积空洞区域补全与单独部分区域分离并剔除
ArcGIS矢量面要素中零碎小面积空洞区域补全与单独部分区域分离并剔除
|
2月前
【每日一题Day162】LC1637两点之间不包含任何点的最宽垂直区域 | 排序
【每日一题Day162】LC1637两点之间不包含任何点的最宽垂直区域 | 排序
105 0
|
7月前
两个或者多个图片上下之间有空隙
两个或者多个图片上下之间有空隙
|
12月前
|
定位技术 API 容器
百度地图API开发:map.getDistance计算两点之间的距离(直线距离)
百度地图API开发:map.getDistance计算两点之间的距离(直线距离)
769 0
|
12月前
|
C++
C++ 计算一个区域的内切圆, 区域内的一个点
C++ 计算一个区域的内切圆, 区域内的一个点
79 0
|
存储
ArcGIS根据相邻关系提取相邻面&提取面公共线
这是一份建筑面数据建筑面数据,这个面图层中有很多个面,有些面相互挨着的,有些单独分布,不与其他任何面相邻。如何把有相邻面的面全部给提出来
153 0

热门文章

最新文章