要求：时间复杂度O(n).
思路：看到时间复杂度为O(n)，肯定排除了常见的基于比较的排序，比如冒泡、快排等等。进而想到桶排序来解决此问题。首先数组有n个数，我们拿n+1个桶，首先遍历下数组找出最大值和最小值，将最小值放在第一个桶中，将最大值放在最后一个桶中，因此中间桶必定有空桶（可能有多个空桶）。注意：空桶左侧的第一个桶的最大值和空桶右侧的第一个桶的最小值在排序后肯定是相邻的，这两个数相减肯定大于单独一个桶内的范围range。相邻数可以来自于一个桶内之间的相邻数，也可以来自于桶于桶之间的数。我们可以不用考虑一个桶内的相邻两数的差值，因为肯定小于桶内的范围range。而有空桶的存在，空桶右侧的最小值减去空桶左侧的最大值一定是数组中相邻两数的最大差值。因此，我们只需记录桶内出现的最大值和最小值，里面的数据不需要管，更不需要排序。答案来自于空桶两侧的非空桶最小值减去最大值？不一定！例如桶ABC，A的数据范围0~9，B的数据范围10~19，C的数据范围是20~29，B为空桶，A桶放了数据9，C桶放了数据20，差值为11。D桶数据范围为30~39，E桶数据范围为40~49，D桶数据为30，E桶数据为49，两者差值为19，用非空桶的目的是我们不需要关注桶内部的差值（因为不会超过range）。所以，两数最大差值不一定来自空桶两侧的非空桶差值。
public static int maxGap(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
int len = nums.length;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < len; i++) {
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]);
}
if (min == max) {
return 0;
}
boolean[] hasNum = new boolean[len + 1]; //统计每个桶是否为空
int[] maxs = new int[len + 1];//统计每个桶的最大值
int[] mins = new int[len + 1];//统计每个桶的最小值
int bid = 0;
for (int i = 0; i < len; i++) {
bid = bucket(nums[i], len, min, max);
mins[bid] = hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums[i];
maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums[i];
hasNum[bid] = true;
}
int res = 0;
int lastMax = maxs[0];
int i = 1;
for (; i <= len; i++) {
if (hasNum[i]) {
res = Math.max(res, mins[i] - lastMax); //计算每个相邻的非空桶差值
lastMax = maxs[i];
}
}
return res;
}
//给一个数num，计算进入哪个桶
public static int bucket(long num, long len, long min, long max) {
return (int) ((num - min) * len / (max - min));
}