智力题

在实数轴上有n个点，x1，x2.。。。xn，这n个数互不相等，且无序，在这n个点中，求与相邻的两个点的距离的最大差值，要求时间复杂度是线性的。

解法：

1.首先找出最大的数Xn和最小的数Xm，然后求出他们的差值记为len.这个过程的时间复杂度为O(n)

2.将xm和xn看做长度为len的线段的2个端点，将该线段分为n-1个子线段，将剩下的n-1个点按他们跟xm的距离放入这n-1子线段里。每个子线段记录该线段里的最小值和最大值。这个过程的时间复杂度为O(n)

3.根据鸽笼原理，可以知道n-1子线段至少有一个子线段里没有任何点，所以最大差值不会出现在子线段中。现在从小到大，扫描这n-1个子线段，扫描过程中记录2个值，lp和maxlen，这个过程的伪代码如下：

lp=xm

maxlen=-1

for 子线段 in n-1个子线段

if 子线段为空

continue

else

x=子线段里的最小点

m=x-lp

if m>maxlen

maxlen=m

lp=子线段里的最大点

maxlen的最后结果便是要求的值

这个过程的时间复杂度为O(n)