1637.md

title	description	keywords
1637. 两点之间不包含任何点的最宽垂直区域	LeetCode 1637. 两点之间不包含任何点的最宽垂直区域题解，Widest Vertical Area Between Two Points Containing No Points，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 1637. 两点之间不包含任何点的最宽垂直区域 两点之间不包含任何点的最宽垂直区域 Widest Vertical Area Between Two Points Containing No Points 解题思路 数组 排序

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

🟢 Easy  🔖  数组 排序  🔗 力扣 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	不含特殊楼层的最大连续楼层数		数组 排序	🟠	🀄️ 🔗