给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0。
class Solution {
public int maximumGap(int[] nums) {
if(nums.length < 2) return 0;
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
int n = nums.length;
for (int d: nums) {
max = Math.max(max, d);
min = Math.min(min, d);
}
int size = (max - min) / n + 1;//桶大小
int bucket_nums = (max - min) / size + 1;//桶个数
int []bucket_min = new int[bucket_nums];
int []bucket_max = new int[bucket_nums];
for(int i = 0; i < bucket_nums; i++){
bucket_min[i] = Integer.MAX_VALUE;
bucket_max[i] = Integer.MIN_VALUE;
}
HashSet<Integer> hs = new HashSet<Integer>();
for (int d : nums) {
int idx = (d - min) / size;//桶索引
bucket_min[idx] = Math.min(bucket_min[idx], d);
bucket_max[idx] = Math.max(bucket_max[idx], d);
hs.add(idx);
}
int pre = 0;
int res = 0;
for (int i = 1; i < bucket_nums; ++i) {
if (!hs.contains(i)) continue;//判断桶内是否有元素
res = Math.max(res, bucket_min[i] - bucket_max[pre]);
pre = i;
}
return res;
}
}
