給定一個無序的數(shù)組扒披，找出數(shù)組在排序之后沸停，相鄰元素之間最大的差值。
如果數(shù)組元素個數(shù)小于 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;//桶個數(shù)
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;//判斷桶內(nèi)是否有元素
res = Math.max(res, bucket_min[i] - bucket_max[pre]);
pre = i;
}
return res;
}
}
