这道题会用到Bucket Sort的概念。 【一看题目就发现如果用Sort的话起码nlogn, 太慢了】
假设Array有N个数。 每个Bucket里代表一个interval. 然后根据数字大小扔到对应范围的Bucket里。
桶的个数 = (最大数减最小数)/N +1
比如[1,1,1,5,5,5] (5-1)/6=0 然后再加一 保证我们至少有一个桶。
Interval= (num-mini)/ 桶的个数。
如果数组是uniform gap.[2,4,6,8,10] 这种，我们知道gap = (max-min)/(n-1)
但是如果不是uniform，绝对会有一个gap比(max-min)/(n-1)大的， 要不然无法cancel effects of 比(max-min)/(n-1)小的。所以如果我们把bucket size限制小于等于(max-min)/(n-1)。 也就是同一个bucket内部的elements的gap无论如何都不是不是全数组里最大的gap。 于是，我们只要在bucket和bucket之间找就可以了。
然后我们用两个数字 int[] min =[....], int[] arr=[...]
把每个bucket的min, max 放进去。
min[0]
max[0] 表示bucket 0的最小和最大值。
然后把每个bucket直接互相相减: bucket A的最小值和bucketB的最大值 相减得到差。
最后取最大差值。
代码实现：
