1637. Widest Vertical Area Between Two Points Containing No Points：LeetCode 最大垂直间隙的排序解法全解析

1637. Widest Vertical Area Between Two Points Containing No Points：LeetCode 最大垂直间隙的排序解法全解析

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

导读

本文围绕 LeetCode 1637「不含任何点的最宽垂直区域」展开，系统讲解从暴力枚举到基于排序的线性扫描两种解法，并覆盖 9 种主流语言的完整实现。本文是 NeetCode 题解仓库（leetcode1/leetcode）中 widest-vertical-area-between-two-points-containing-no-points.md 的深度展开版本，结合仓库内 Java、Kotlin 的实际提交代码验证结论。读完本文，你将掌握“排序 + 相邻差值”这一经典优化范式，并能识别该题中常见的三类编码误区。

1. 问题回顾与前置知识

题目要求：给定平面上的n个点（以二维数组形式给出），求一条垂直（即平行于 y 轴）的带状区域，使得该区域内不包含任何点，并返回这条带状区域的最大宽度。宽度即两侧竖线 x 坐标之差的绝对值。

关键认知是：这是一个一维问题。虽然输入是二维坐标，但 y 坐标对答案完全没有影响——垂直区域的“宽度”只取决于 x 坐标的跨度，区域内“没有点”也仅指没有点的 x 坐标落在开区间内。

动手解题前，需要具备两项基础能力：

• 排序（Sorting）：按 x 坐标排序后，最大间隙必然出现在相邻点之间，这是整个优化解的核心洞察；
• 数组遍历（Array Iteration）：扫描已排序数组，逐个计算相邻 x 坐标的差值并维护最大值。

仓库中的实际提交 java/1637-widest-vertical-area-between-two-points-containing-no-points.java 与 kotlin/1637-widest-vertical-area-between-two-points-containing-no-points.kt 均采用排序解法，可作为正确性参照。

2. 解法一：暴力枚举（Brute Force）

2.1 直觉（Intuition）

最直观的思路是枚举所有点对：对于任意两个点i和j，它们的 x 坐标构成一个候选垂直区域。要判定该区域是否“不含任何点”，需要再遍历一次全部点，检查是否存在第三个点的 x 坐标严格落在二者之间。若不存在，则|x1 - x2|就是一个合法宽度。遍历所有点对并取最大值即为答案。

该解法能保证正确，但由于三重循环的存在，只适合规模很小的输入。

2.2 算法步骤（Algorithm）

1. 用两层嵌套循环遍历所有点对(i, j)，取它们的 x 坐标为x1、x2；
2. 对每个点对，再遍历一次所有点k（跳过k == i与k == j），检查是否存在min(x1, x2) < x3 < max(x1, x2)；
3. 若存在这样的点，则该区域无效；否则用abs(x1 - x2)更新答案；
4. 返回所有合法点对中的最大宽度。

2.3 多语言实现

下面给出原文档中完整的 9 语言暴力解法实现。

class Solution: def maxWidthOfVerticalArea(self, points: List[List[int]]) -> int: n = len(points) res = 0 for i in range(1, n): x1 = points[i][0] for j in range(i): x2 = points[j][0] hasPoints = False for k in range(n): if k == i or k == j: continue x3 = points[k][0] if x3 > min(x1, x2) and x3 < max(x1, x2): hasPoints = True break if not hasPoints: res = max(res, abs(x1 - x2)) return res

public class Solution { public int maxWidthOfVerticalArea(int[][] points) { int n = points.length, res = 0; for (int i = 1; i < n; i++) { int x1 = points[i][0]; for (int j = 0; j < i; j++) { int x2 = points[j][0]; boolean hasPoints = false; for (int k = 0; k < n; k++) { if (k == i || k == j) continue; int x3 = points[k][0]; if (x3 > Math.min(x1, x2) && x3 < Math.max(x1, x2)) { hasPoints = true; break; } } if (!hasPoints) { res = Math.max(res, Math.abs(x1 - x2)); } } } return res; } }

class Solution { public: int maxWidthOfVerticalArea(vector<vector<int>>& points) { int n = points.size(), res = 0; for (int i = 1; i < n; i++) { int x1 = points[i][0]; for (int j = 0; j < i; j++) { int x2 = points[j][0]; bool hasPoints = false; for (int k = 0; k < n; k++) { if (k == i || k == j) continue; int x3 = points[k][0]; if (x3 > min(x1, x2) && x3 < max(x1, x2)) { hasPoints = true; break; } } if (!hasPoints) { res = max(res, abs(x1 - x2)); } } } return res; } };

class Solution { /** * @param {number[][]} points * @return {number} */ maxWidthOfVerticalArea(points) { let n = points.length, res = 0; for (let i = 1; i < n; i++) { let x1 = points[i][0]; for (let j = 0; j < i; j++) { let x2 = points[j][0]; let hasPoints = false; for (let k = 0; k < n; k++) { if (k === i || k === j) continue; let x3 = points[k][0]; if (x3 > Math.min(x1, x2) && x3 < Math.max(x1, x2)) { hasPoints = true; break; } } if (!hasPoints) { res = Math.max(res, Math.abs(x1 - x2)); } } } return res; } }

public class Solution { public int MaxWidthOfVerticalArea(int[][] points) { int n = points.Length, res = 0; for (int i = 1; i < n; i++) { int x1 = points[i][0]; for (int j = 0; j < i; j++) { int x2 = points[j][0]; bool hasPoints = false; for (int k = 0; k < n; k++) { if (k == i || k == j) continue; int x3 = points[k][0]; if (x3 > Math.Min(x1, x2) && x3 < Math.Max(x1, x2)) { hasPoints = true; break; } } if (!hasPoints) { res = Math.Max(res, Math.Abs(x1 - x2)); } } } return res; } }

func maxWidthOfVerticalArea(points [][]int) int { n := len(points) res := 0 for i := 1; i < n; i++ { x1 := points[i][0] for j := 0; j < i; j++ { x2 := points[j][0] hasPoints := false for k := 0; k < n; k++ { if k == i || k == j { continue } x3 := points[k][0] if x3 > min(x1, x2) && x3 < max(x1, x2) { hasPoints = true break } } if !hasPoints { res = max(res, abs(x1-x2)) } } } return res } func abs(x int) int { if x < 0 { return -x } return x }

class Solution { fun maxWidthOfVerticalArea(points: Array<IntArray>): Int { val n = points.size var res = 0 for (i in 1 until n) { val x1 = points[i][0] for (j in 0 until i) { val x2 = points[j][0] var hasPoints = false for (k in 0 until n) { if (k == i || k == j) continue val x3 = points[k][0] if (x3 > minOf(x1, x2) && x3 < maxOf(x1, x2)) { hasPoints = true break } } if (!hasPoints) { res = maxOf(res, kotlin.math.abs(x1 - x2)) } } } return res } }

class Solution { func maxWidthOfVerticalArea(_ points: [[Int]]) -> Int { let n = points.count var res = 0 for i in 1..<n { let x1 = points[i][0] for j in 0..<i { let x2 = points[j][0] var hasPoints = false for k in 0..<n { if k == i || k == j { continue } let x3 = points[k][0] if x3 > min(x1, x2) && x3 < max(x1, x2) { hasPoints = true break } } if !hasPoints { res = max(res, abs(x1 - x2)) } } } return res } }

impl Solution { pub fn max_width_of_vertical_area(points: Vec<Vec<i32>>) -> i32 { let n = points.len(); let mut res = 0; for i in 1..n { let x1 = points[i][0]; for j in 0..i { let x2 = points[j][0]; let mut has_points = false; for k in 0..n { if k == i || k == j { continue; } let x3 = points[k][0]; if x3 > x1.min(x2) && x3 < x1.max(x2) { has_points = true; break; } } if !has_points { res = res.max((x1 - x2).abs()); } } } res } }

2.4 复杂度分析

• 时间复杂度：$O(n^3)$。两层循环枚举点对，第三层循环验证区间内是否有点；
• 空间复杂度：$O(1)$。仅使用常数个辅助变量，没有额外数据结构。

三重循环意味着当n达到上万级别时运算量将不可接受，因此暴力解仅适合验证思路或小数据场景。

3. 解法二：排序 + 相邻差值（Sorting）

3.1 直觉（Intuition）

这是本题的核心洞察：按 x 坐标排序后，任何不包含点的垂直区域，其左右边界必然对应一对“相邻”的点。

理由如下：把所有点按 x 坐标从小到大排列后，若取一对非相邻的点作为区域边界，那么位于二者之间的那些点（至少一个）的 x 坐标必然严格落在开区间内，该区域因此“包含点”而非法。反之，任意一对相邻点的 x 坐标之间不存在任何其他点的 x 坐标，它们构成的垂直区域天然为空，宽度即为两点 x 坐标之差。

因此，问题被化简为：排序后扫描一遍，求相邻点 x 坐标差值的最大值。

3.2 算法步骤（Algorithm）

1. 按 x 坐标对points数组排序；
2. 遍历排序后数组的相邻点对(i, i+1)；
3. 计算points[i+1][0] - points[i][0]；
4. 返回所有差值中的最大值。

3.3 多语言实现

class Solution: def maxWidthOfVerticalArea(self, points: List[List[int]]) -> int: points.sort() res = 0 for i in range(len(points) - 1): res = max(res, points[i + 1][0] - points[i][0]) return res

public class Solution { public int maxWidthOfVerticalArea(int[][] points) { Arrays.sort(points, Comparator.comparingInt(a -> a[0])); int res = 0; for (int i = 0; i < points.length - 1; i++) { res = Math.max(res, points[i + 1][0] - points[i][0]); } return res; } }

class Solution { public: int maxWidthOfVerticalArea(vector<vector<int>>& points) { sort(points.begin(), points.end(), [](const auto& a, const auto& b) { return a[0] < b[0]; }); int res = 0; for (int i = 0; i < points.size() - 1; i++) { res = max(res, points[i + 1][0] - points[i][0]); } return res; } };

class Solution { /** * @param {number[][]} points * @return {number} */ maxWidthOfVerticalArea(points) { points.sort((a, b) => a[0] - b[0]); let res = 0; for (let i = 0; i < points.length - 1; i++) { res = Math.max(res, points[i + 1][0] - points[i][0]); } return res; } }

public class Solution { public int MaxWidthOfVerticalArea(int[][] points) { Array.Sort(points, (a, b) => a[0].CompareTo(b[0])); int res = 0; for (int i = 0; i < points.Length - 1; i++) { res = Math.Max(res, points[i + 1][0] - points[i][0]); } return res; } }

func maxWidthOfVerticalArea(points [][]int) int { sort.Slice(points, func(i, j int) bool { return points[i][0] < points[j][0] }) res := 0 for i := 0; i < len(points)-1; i++ { res = max(res, points[i+1][0]-points[i][0]) } return res }

class Solution { fun maxWidthOfVerticalArea(points: Array<IntArray>): Int { points.sortBy { it[0] } var res = 0 for (i in 0 until points.size - 1) { res = maxOf(res, points[i + 1][0] - points[i][0]) } return res } }

class Solution { func maxWidthOfVerticalArea(_ points: [[Int]]) -> Int { let sortedPoints = points.sorted { $0[0] < $1[0] } var res = 0 for i in 0..<sortedPoints.count - 1 { res = max(res, sortedPoints[i + 1][0] - sortedPoints[i][0]) } return res } }

impl Solution { pub fn max_width_of_vertical_area(mut points: Vec<Vec<i32>>) -> i32 { points.sort_unstable_by_key(|p| p[0]); let mut res = 0; for i in 0..points.len() - 1 { res = res.max(points[i + 1][0] - points[i][0]); } res } }

3.4 仓库源码佐证

仓库中该题的 Java 提交与文档思路完全一致，且在细节上更精简——它直接以索引 1 起步，每次与前一索引比较，避免了i + 1的越界顾虑：

// java/1637-widest-vertical-area-between-two-points-containing-no-points.java class Solution { public int maxWidthOfVerticalArea(int[][] points) { Arrays.sort(points, (p1, p2) -> p1[0] - p2[0]); int res = 0; for(int i = 1; i < points.length; i++){ res = Math.max(res, points[i][0] - points[i-1][0]); } return res; } }

Kotlin 提交则使用sortBy { it[0] }按 x 排序，并将结果初值设为-1（在n == 1的边界下也能稳定返回-1之外的最小差值，实际场景中所有差值非负，最终答案仍为最大差值）：

// kotlin/1637-widest-vertical-area-between-two-points-containing-no-points.kt class Solution { fun maxWidthOfVerticalArea(points: Array<IntArray>): Int { points.sortBy { it[0] } var res = -1 for (i in 1 until points.size) res = maxOf(res, points[i][0] - points[i - 1][0]) return res } }

两份实现与文档中的排序解法在算法思想上完全一致，可相互印证：排序后仅需一次线性扫描即可得到答案。

3.5 复杂度分析

• 时间复杂度：$O(n \log n)$，瓶颈在于排序；
• 空间复杂度：$O(1)$ 或 $O(n)$，取决于所用排序算法的实现（如原地快排为 $O(\log n)$ 栈空间，归并等非原地排序则可能为 $O(n)$）。

4. 两种解法对比

排序解不仅快，而且代码更短、更不易出错，是本体的推荐实现。

5. 常见误区（Common Pitfalls）

5.1 误用 y 坐标

题目求的是垂直区域宽度，只关心 x 轴的跨度。初学者常误用 y 坐标或计算二维距离：

# Wrong: using y-coordinate width = abs(points[i][1] - points[j][1]) # Correct: using x-coordinate only width = abs(points[i][0] - points[j][0])

5.2 排序后仍检查所有点对

排序后最大间隙必然出现在相邻点之间，非相邻点对之间必然夹着至少一个点，区域非法。若排序后仍双重循环枚举所有点对，虽然答案不变，但复杂度退化到 $O(n^2)$：

# Wrong: checking all pairs after sorting for i in range(n): for j in range(i + 1, n): res = max(res, points[j][0] - points[i][0]) # Correct: only check adjacent pairs for i in range(n - 1): res = max(res, points[i + 1][0] - points[i][0])

5.3 排序键使用不当

排序时应只以 x 坐标为键。Python 的points.sort()默认会对整个点（先 x 后 y）排序，虽然因为 x 是主键、结果仍然正确，但显式指定key=lambda p: p[0]更清晰地表达意图，也避免依赖默认字典序的隐式行为：

# Correct: sort by x-coordinate (y doesn't affect the answer) points.sort(key=lambda p: p[0])

同理，在 Java/C++ 等语言中，若自定义比较器时误按 y 坐标比较，将直接得到错误答案。

6. 小结

LeetCode 1637 是一道“伪装成几何题”的排序应用题：一旦意识到垂直区域宽度只依赖 x 坐标、且最大空区域必然由排序后的相邻点界定，问题就从三维暴力降维成一次排序加一次扫描。掌握这种“先排序、再检查相邻元素”的思维模式，可以迁移到 Minimum Difference Between Highest and Lowest of K Scores、K Closest Points to Origin 等大量基于排序的题目中。

如需在本地运行验证，可参考仓库内 Java 与 Kotlin 的完整提交文件（Java 实现、Kotlin 实现），或按本文给出的任意语言代码在 LeetCode 对应题号下提交测试。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode