第一种方法：
计数排序后，然后找出两两之间的最大差值
计数排序的时间复杂度是O（N）
public class CountSort {
public static void main(String[] args) {
int[] arr = new int[] { , , , , , , , , };
sort(arr);
Arrays.stream(arr).forEach(x -> System.out.print(x + " "));
//计算出相邻两个元素的最大差值
int maxGap = Integer.MIN_VALUE;
for(int i = ;i<arr.length ; i++) {
int gap = arr[i]-arr[i-];
if(gap > maxGap) {
maxGap = gap;
}
}
System.out.println();
System.out.println(maxGap);
}
public static void sort(int [] arr ) {
//获取最大值和最小值
int min = arr[];
int max = arr[];
for ( int i = ; i < arr.length; i++) {
if(arr[i] < min) {
min = arr[i];
}
if(arr[i] > max) {
max = arr[i];
}
}
//初始化一个桶，并向桶里装数据
int [] bucket = new int[max-min+];
for(int j= ; j<arr.length; j++) {
bucket[arr[j]-min]++;
}
//从桶里取数据，将原数组排序
int index = ;
for(int i = ;i <bucket.length;i++) {
while(bucket[i]-- > ) {
arr[index++] = i+min;
}
}
}
}
第二种方法：
1 使用桶的思想，设置N+1个桶，必然有一个空桶，那么就排除了最大差值在一个桶内，因为空桶两侧的差距肯定大于桶内的差距
2 但是最大差值不一定就是空桶左侧max和空桶右侧min,需要依次遍历求差值
public class MaxGap {
public static void main(String[] args) {
int[] arr = new int[] { , , , , , , , , };
int res = getMaxGap(arr);
System.out.println(res);
}
public static int getMaxGap(int [] nums) {
//获取最大值和最小值
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int len = nums.length;
for (int i = ; i < len; i++) {
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]);
}
if (min == max) {
return ;
}
//假如原数组有N个元素，声明三个长度都是N+1的数组，代表着N+1个桶，序号是从0到n
boolean[] hasNum = new boolean[len + ];
int[] maxs = new int[len + ];
int[] mins = new int[len + ];
//遍历原数组，将数组中的元素分别放到这n+1个桶中
int bid = ;
for (int i = ; 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;
}
//遍历这n+1个桶，将非空桶的最小值和该桶的上一个非空桶的最大值比较，两者之差中的最大值即为所求
int res = ;
int lastMax = maxs[];
for (int i = ; i <= len; i++) {
if (hasNum[i]) {
res = Math.max(res, mins[i] - lastMax);
lastMax = maxs[i];
}
}
return res;
}
//计算桶的下标位置
public static int bucket(long num, long len, long min, long max) {
return (int) ((num - min) * len / (max - min));
}
}
