1637. 两点之间不包含任何点的最宽垂直区域
1637. 两点之间不包含任何点的最宽垂直区域
题目
Given n
points
on a 2D plane where points[i] = [xi, yi]
, Return _ the widest vertical area between two points such that no points are inside the area._
A vertical area is an area of fixed-width extending infinitely along the y-axis (i.e., infinite height). The widest vertical area is the one with the maximum width.
Note that points on the edge of a vertical area are not considered included in the area.
Example 1:
Input: points = [[8,7],[9,9],[7,4],[9,7]]
Output: 1
Explanation: Both the red and the blue area are optimal.
Example 2:
Input: points = [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]]
Output: 3
Constraints:
n == points.length
2 <= n <= 10^5
points[i].length == 2
0 <= xi, yi <= 10^9
题目大意
给你 n
个二维平面上的点 points
,其中 points[i] = [xi, yi]
,请你返回两点之间内部不包含任何点的 最宽垂直区域 的宽度。
垂直区域 的定义是固定宽度,而 y 轴上无限延伸的一块区域(也就是高度为无穷大)。 最宽垂直区域 为宽度最大的一个垂直区域。
请注意,垂直区域 边上 的点 不在 区域内。
示例 1:
![](https://assets.leetcode-cn.com/aliyun-lc- upload/uploads/2020/10/31/points3.png)
输入: 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
解题思路
points
中的每个点是一个二维坐标[x, y]
。关注横坐标x
,忽略纵坐标y
。按横坐标
x
对点进行升序排序,以便计算相邻点之间的间距。遍历排序后的横坐标,计算相邻横坐标之间的差值,取最大的差值作为结果。
复杂度分析
- 时间复杂度:
O(n log n)
,其中n
是点的数量,排序的时间开销。 - 空间复杂度:
O(1)
,排序是原地排序,不需要额外的空间。
代码
/**
* @param {number[][]} points
* @return {number}
*/
var maxWidthOfVerticalArea = function (points) {
// 按横坐标升序排序
points.sort((a, b) => a[0] - b[0]);
let widest = 0;
// 遍历相邻横坐标,找出最大差值
for (let i = 1; i < points.length; i++) {
widest = Math.max(widest, points[i][0] - points[i - 1][0]);
}
return widest;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
164 | 最大间距 | 数组 桶排序 基数排序 1+ | 🟠 | 🀄️ 🔗 | |
2274 | 不含特殊楼层的最大连续楼层数 | 数组 排序 | 🟠 | 🀄️ 🔗 |