计算排序后的最大间距

最大间隔

已知整数数组A的索引范围从0到N-1，请计算该数组经过排序后的最大间距。
例如，在给定的数据序列中（如序列[1,7,…]），其最大间距为4。
当对原始数据进行升序排列之后（如排列结果为[举例展示排序后的数组]），计算相邻元素之间的差值即可得到最大的间距差值（即为上述例子中的结果）。
显然地，在对原始数据进行升序排列之后（即步骤如下所示），所得到的结果就是所要求解的最大间距。
那么是否有更高效的方法？

问题分析

设 N 个数据的最大值与最小值分别为 max 和 min , 则这些数据构成 N-1 个区间.
若这些数值严格均匀分布, 则所有区间长度均为 \frac{max - min}{n - 1} 并达到最小.
若这些数值并非严格均匀分布, 则最大的区间长度必定超过 \frac{max - min}{n - 1}.

解决思路

将N个数值按照间距进行划分得到N-1个区间，则同一区间内的任意两个数值之间的距离均不超过该区间的间距。若有某一个区间内没有任何数值，则该区间的实际意义为零；若有多个相邻的空闲区间相连，则合并为一个空闲区域并忽略其实际意义。由此可见，在计算最大间隔时无需考虑空闲区域的存在

桶的数目

同时认为N-1个桶作为理论值可能会导致某些桶的数量比其他桶多出一个单位。
例如，在处理7个数值的