给定一个整型数组arr，返回排序后的相邻两数的最大差值
举例：
arr = [9,3,1,10]。如果排序，结果为[1,3,9,10]，9和3的差为最大差值。故返回6。
arr = [5,5,5,5]。返回0。
这道题是阿里往年的一道面试题，据说把ACM World Final选手都难住了，因为正式的ACM比赛中判题系统往往不会仅让O(n)的算法AC，而卡住O(nlogn)的算法，所以ACM选手普遍缺乏对O(logn)那部分复杂度的优化训练。
而本题如果用普通的比较排序方法来实现，时间复杂度是O(nlogn)，这并不是一个能让面试官满意的答案。
要做到O(n)的时间复杂度，考虑利用桶排序的思想，不过不是直接进行排序。
假设arr的长度为n，我们准备n+1个桶，桶号 0 ~ n。对于arr中的任意一个数num，利用映射函数(num - min) * n / (max - min)将其映射到对应的桶中。通过这种映射，min会单独占据0号桶，max会单独占据n号桶，当把所有的n个数放进n+1个桶中，中间必然有个桶是空的。因此，排序后的最大差值只可能来自某个非空桶中的最小值减去前一个非空桶中的最大值。
具体过程请参看如下代码：
public class ArrayMaxGap {
/**
* 映射函数，将数组元素映射到桶中，使用long类型防止相乘时溢出
*
* @param num
* @param n
* @param min
* @param max
* @return
*/
public static int mapToBucket(long num, long n, long min, long max) {
return (int) ((num - min) * n / (max - min));
}
public static int getMaxGap(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
int n = nums.length;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) { // 找到数组的最小值和最大值
if (nums[i] < min) {
min = nums[i];
}
if (nums[i] > max) {
max = nums[i];
}
}
if (min == max) {
return 0;
}
boolean[] hasNum = new boolean[n + 1]; // 标识桶中是否有数
int[] bMins = new int[n + 1]; // 桶中最小值
int[] bMaxs = new int[n + 1]; // 桶中最大值
for (int i = 0; i < n; i++) { // 统计每个桶中的最小值和最大值
int b = mapToBucket(nums[i], n, min, max); // 当前元素所在的桶
if (hasNum[b]) {
if (nums[i] < bMins[b]) {
bMins[b] = nums[i];
}
if (nums[i] > bMaxs[b]) {
bMaxs[b] = nums[i];
}
} else {
bMins[b] = bMaxs[b] = nums[i];
hasNum[b] = true;
}
}
int maxGap = 0;
int lastbMax = bMaxs[0]; // 前一个非空桶的最大值，第一个非空桶必是0号桶
int b = 1;
while (b <= n) {
if (hasNum[b]) {
if (bMins[b] - lastbMax > maxGap) { // 当前非空桶的最小值与上一个非空桶的最大值做差，取最大差值
maxGap = bMins[b] - lastbMax;
}
lastbMax = bMaxs[b];
}
b++;
}
return maxGap;
}
public static void main(String[] args) {
int[] arr = new int[]{9, 3, 1, 10};
System.out.println(getMaxGap(arr));
}
}
牛客上的这道相邻最大差值，可以将代码提交上去跑跑。
