跳至主要內容

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


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

🟢   🔖  数组 排序  🔗 力扣open in new window LeetCodeopen in new window

题目

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

解题思路

  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+🟠🀄️open in new window 🔗open in new window
2274不含特殊楼层的最大连续楼层数数组 排序🟠🀄️open in new window 🔗open in new window