1637. Widest Vertical Area Between Two Points Containing No PointsLeetCode 最大垂直间隙的排序解法全解析【免费下载链接】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 Force2.1 直觉Intuition最直观的思路是枚举所有点对对于任意两个点i和j它们的 x 坐标构成一个候选垂直区域。要判定该区域是否“不含任何点”需要再遍历一次全部点检查是否存在第三个点的 x 坐标严格落在二者之间。若不存在则|x1 - x2|就是一个合法宽度。遍历所有点对并取最大值即为答案。该解法能保证正确但由于三重循环的存在只适合规模很小的输入。2.2 算法步骤Algorithm用两层嵌套循环遍历所有点对(i, j)取它们的 x 坐标为x1、x2对每个点对再遍历一次所有点k跳过k i与k j检查是否存在min(x1, x2) x3 max(x1, x2)若存在这样的点则该区域无效否则用abs(x1 - x2)更新答案返回所有合法点对中的最大宽度。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 respublic 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(vectorvectorint 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: ArrayIntArray): 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: VecVeci32) - 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. 解法二排序 相邻差值Sorting3.1 直觉Intuition这是本题的核心洞察按 x 坐标排序后任何不包含点的垂直区域其左右边界必然对应一对“相邻”的点。理由如下把所有点按 x 坐标从小到大排列后若取一对非相邻的点作为区域边界那么位于二者之间的那些点至少一个的 x 坐标必然严格落在开区间内该区域因此“包含点”而非法。反之任意一对相邻点的 x 坐标之间不存在任何其他点的 x 坐标它们构成的垂直区域天然为空宽度即为两点 x 坐标之差。因此问题被化简为排序后扫描一遍求相邻点 x 坐标差值的最大值。3.2 算法步骤Algorithm按 x 坐标对points数组排序遍历排序后数组的相邻点对(i, i1)计算points[i1][0] - points[i][0]返回所有差值中的最大值。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 respublic 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(vectorvectorint 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[i1][0]-points[i][0]) } return res }class Solution { fun maxWidthOfVerticalArea(points: ArrayIntArray): 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: VecVeci32) - 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: ArrayIntArray): 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. 两种解法对比维度暴力枚举排序 相邻差值核心思路枚举所有点对并验证区间是否为空排序后只检查相邻点对的 x 差值时间复杂度$O(n^3)$$O(n \log n)$空间复杂度$O(1)$$O(1)$ 或 $O(n)$取决于排序实现代码复杂度三重循环逻辑繁琐一次排序 一次线性扫描适用场景仅用于小数据验证正确性面试与竞赛的标准最优解排序解不仅快而且代码更短、更不易出错是本体的推荐实现。5. 常见误区Common Pitfalls5.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 是主键、结果仍然正确但显式指定keylambda p: p[0]更清晰地表达意图也避免依赖默认字典序的隐式行为# Correct: sort by x-coordinate (y doesnt affect the answer) points.sort(keylambda 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考