LeetCode 题解工作台
两点之间不包含任何点的最宽垂直区域
给你 n 个二维平面上的点 points ，其中 points[i] = [x i , y i ] ，请你返回两点之间内部不包含任何点的 最宽垂直区域 的宽度。 垂直区域 的定义是固定宽度，而 y 轴上无限延伸的一块区域（也就是高度为无穷大）。 最宽垂直区域 为宽度最大的一个垂直区域。 请注意，垂直…
2
题型
6
代码语言
3
相关题
当前训练重点
简单 · 数组·排序
答案摘要
我们可以对数组 按照 升序排列，获取相邻点之间 的差值的最大值。 时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 为数组 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·排序 题型思路
题目描述
给你 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.length2 <= n <= 105points[i].length == 20 <= xi, yi <= 109
解题思路
方法一：排序
我们可以对数组 按照 升序排列，获取相邻点之间 的差值的最大值。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def maxWidthOfVerticalArea(self, points: List[List[int]]) -> int:
points.sort()
return max(b[0] - a[0] for a, b in pairwise(points))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N \log N) |
| 空间 | O(\log N) |
面试官常问的追问
外企场景- question_mark
Sorting the points is the first step; neglecting it can lead to incorrect width calculation.
- question_mark
Focusing on consecutive x-coordinates reveals the maximum gap; random comparisons fail to leverage the pattern.
- question_mark
Boundary points do not count inside the vertical area; including them will produce off-by-one errors.
常见陷阱
外企场景- error
Attempting nested loops over all points increases time complexity unnecessarily.
- error
Confusing y-coordinates with x-coordinates can lead to incorrect area widths.
- error
Forgetting to exclude boundary points from the vertical area can yield wrong results.
进阶变体
外企场景- arrow_right_alt
Find the widest horizontal area with no points inside by sorting y-coordinates instead.
- arrow_right_alt
Determine the k largest vertical gaps rather than just the maximum width.
- arrow_right_alt
Handle points with duplicate x-coordinates and ensure the area width remains zero for overlapping points.