直线上两点最近距离：排序后只比相邻点
LeetCode 613 · LEAD、排序后相邻差
面试怎么回答
一维最近点对一定是排序后相邻的两点，所以按 x 排序，用 LEAD(x) 取下一个点，MIN(LEAD(x) - x) 就是答案，只需要一次排序。进阶要输出点的编号，就在同一个子查询里把下一个点的编号也 LEAD 出来，再取差值最小的那一行。
先把这段讲顺；面试官追问时，再展开下面的原理和细节。
详细讲解
题意
x 轴上有若干个互不相同的整数坐标点，求最近两点之间的距离。
表结构
- point：x（主键）
思路
一维上最近的两个点一定是排序后相邻的两个点，所以不用两两比较：按 x 排序，用 LEAD 取下一个点，相邻差的最小值就是答案。这把 O(n²) 的自连接变成了一次排序。
参考解法
写法 1：窗口函数：排序后相邻差的最小值
select min(l-x) shortest
from(
select x,lead(x,1,null) over(order by x) l
from point
)t1写法 2：自连接：所有点两两比较
SELECT
MIN(ABS(p1.x - p2.x)) AS shortest
FROM
point p1
JOIN
point p2 ON p1.x != p2.x
;易错点
- 自连接写法每对算两次，数据量大时很慢。