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

🟢   🔖  数组 排序  🔗 力扣 LeetCode

题目

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：

​

输入： 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

解题思路

1. points 中的每个点是一个二维坐标 [x, y]。关注横坐标 x，忽略纵坐标 y。

2. 按横坐标 x 对点进行升序排序，以便计算相邻点之间的间距。

3. 遍历排序后的横坐标，计算相邻横坐标之间的差值，取最大的差值作为结果。

复杂度分析

• 时间复杂度：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	不含特殊楼层的最大连续楼层数		数组 排序	🟠	🀄️ 🔗