高频面试题：
比如：3 1 6 2 7
排序后是：
这道题目借用了桶这个概念，但是没有进行桶排序
N个数准备N+1个桶
中间的数字：把min到max范围等分成N+1份，一个数属于哪号范围，就放到哪个桶里
例如：
排序之后的相邻数字可能在同一个桶，也可能在相邻的桶
15的相邻值，可能来自于11（同一个桶），可能来自于21（相邻桶）
N个数，准备N+1个桶，min放进第0个桶，max放进第N个桶，中间必有一个空桶
空桶左边非空桶的max值，与空桶右边非空桶的min值相邻，且min–max一定大于每个桶所表示的范围【比如一个桶表示10~19，那桶表示的范围是10，这两个值相减一定大于10】
所以在寻找最大差值的时候，不需要考虑同一个桶中的数据，最大差值一定来自于不同桶（前一个桶的max和后一个桶的min）
每个桶不需要统计桶中的所有数，只需要统计桶中的min和max；当然还需要统计一个boolean类型的数据，这个桶里是否为空
（1） 有数字进入某个桶，桶的boolean类型的变量就要从false变为true
（2） 如果是第一次进入桶，那min = max = 这个数
（3） 如果某个数字再次进入了某个桶，就更新这个桶中的min 和max
（4） 然后从1号桶开始（因为0号桶一定非空），如果是空的，跳到下一个桶，如果是非空的，找前一个非空桶。对于每一个非空桶，都找它前一个非空桶的max和当前这个桶的min
（5） min–max记录最大差值
（6） 要求的最大差值一定在其中是最大的，用一个全局变量就可以找到它
提问：为什么不是找那个空桶，计算空桶两侧的非空桶的min–max
答:如下面的情况，最大差值是19；我们提出这个空桶的概念是否定最大差值来自同一个桶
每个桶的三种信息（是否为空、min、max）用三个数组来描述
import java.util.Arrays;
public class MaxGap {
public static void main(String[] args) {
int[] arr ={0,2,15,23,21,67,88,4,99};//答案44
// int[] arr ={1,2,3,6,7};//答案3
System.out.println(maxGap(arr));
}
public static int maxGap(int[] arr){
if (arr.length<2 || arr == null) {
return 0;
}
//1.遍历找到数组中的最小值min最大值max
int min = arr[0];
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i]<min) {
min = arr[i];
}
if (arr[i]>max) {
max = arr[i];
}
}
System.out.println("min = "+min+" max = "+max);
//2.如果数组中是一串相同的数字，差值为0
if (max == min) {
return 0;
}
//3.构造3个桶
int len = arr.length;
boolean[] hasNum = new boolean[len+1];//数组中的默认值是false
int[] mins = new int[len+1];
int[] maxs = new int[len+1];
//4.重新遍历这个数组，找到每个桶中的max、min
for (int i = 0; i < arr.length; i++) {
//看数组中的每一个数字属于几号桶
int bucketNumber = bucket(arr[i], max, min, len);
System.out.println("第"+i+"个数字在第"+bucketNumber+"号桶");
//桶中无数据
if (!hasNum[bucketNumber]) {
mins[bucketNumber] = arr[i];
maxs[bucketNumber] = arr[i];
hasNum[bucketNumber] = true;
}else {//桶中有数据
mins[bucketNumber] = Math.min(arr[i], mins[bucketNumber]);
maxs[bucketNumber] = Math.max(arr[i], maxs[bucketNumber]);
}
}
System.out.println("每个桶中的最小值mins"+Arrays.toString(mins));
System.out.println("每个桶中的最大值maxs"+Arrays.toString(maxs));
System.out.println(Arrays.toString(hasNum));
//找当前桶的min和前一个非空桶的max
int maxGap = 0;
int lastMax = maxs[0];//前一个非空桶的max
for(int i=1; i<hasNum.length; i++){
if (hasNum[i]) {
maxGap = Math.max((mins[i] - lastMax), maxGap);
System.out.println("第"+i+"次最大值为 "+ maxGap);
// if (lastMax - mins[i] > maxGap) {
// maxGap = lastMax - mins[i];
// }
lastMax = maxs[i];
}
}
return maxGap;
}
/**
* 判断一个数字属于几号桶
* @param num 被判断的数字
* @param max 数组中的最大值
* @param min 数组中的最小值
* @param n 数组中的数据量N
*/
public static int bucket(int num, int max, int min,int n){
return (int)(num-min)*(n+1)/(max-min+1);
}
}
