leet_164

题目链接

题解

这道题还是很有意思的。最简单的就是NlogN的排序+O(N)的扫描，但是题目要求是要 常数倍O(N)。思索了很久也没有想到好的解决方法，最后还是网上搜了点线索，才想出来。

假设一个数组[a,b,c,d,e]，如果a,b,c,d,e构成等差数列，相邻两个数的差值是t，则t=(b-a)=(c-b)=(d-c)=(e-d)。假设我们修改c的值，使它在开区间(b,d)之间任意取值(整数)，很容易发现，两个数之间的最大差值一定大于t（离左边距离近了但离右边距离就远了）。也就是说我们可以得出一个结论，一个有序的a到b的数组，假设有N个元素，如果这N个元素排列成等差数列，那么相邻两个数的最大差值最小，为等差数列的公差。如果不构成等差数列，那么最大差值一定大于等差数列的公差。

得出这个结论有什么用呢？利用这个结论我们可以有一种非常巧妙的解决方法，我们可以利用桶排序的思想，把数组分成M个桶，每个桶的长度刚好是公差t。对每个桶进行排序之后你会发现，由于当且仅当所有元素构成等差数列，它们的最大差值才可能是公差t，其它情况下都大于公差t。而又由于每个桶长度为t，这个桶中理论上的最大值和最小值的差不超过t，因此，最后的结果一定是某两个桶之间最小值和最大值的差。

比如桶长度为10，桶1对[0,9]排序，最大值为7，桶2对[10,19]排序，最小值为16。这时可能的最大差就是桶2的最小值减去桶1的最大值(16-7=9)。最后需要注意的是

• 每个桶不需要真的排序，只需要记录这个范围里的最大与最小值
• 如果一个桶没有值，要把它与之前的桶合并。