-
前言 ：
想写些东西记录自己所学的收获。 -
先上题目 ：
- 思路：
- 比较器
最简单的按排序之后再逐个遍历找出最大差值，但这显然不符合题目要求。 不过这个思路可以当成比较器来用，来检测之后写的代码是否是否要求。
public static int comparator(int[] nums) { if(nums == null || nums.length < 2) { return 0; } Arrays.sort(nums); int gap = Integer.MIN_VALUE; for(int i = 1; i < nums.length; i++) { gap = Math.max(nums[i]-nums[i-1], gap); } return gap; }- 桶排序的思想。
假如有N个数，则需要N+1个桶。 这里桶的序号为0开始计数，当然也可以从1开始。 每个桶记录自己桶是否放进来过数字（boolean类型），记录自己桶的最大值和最小值。
先遍历一遍数组，找出最大值和最小值。如果最大最小值相等，则最大差值是0。 不相等在进行之后操作。 最大值（单独）放入最后一个桶（即第N个桶0），最小值放入最前面的那个桶（即第0个桶）。每个桶都装等区间的数，或者说每个装的 数的范围 是 （最大值-最小值）/ N。
在说说为什么要N+1个桶：
因为这样可以排除最大差值来自桶一个桶的情况。
因为N个数，放N+1个桶，必然最少有一个桶是空桶。那么最大差值就可能来自空桶的左右两侧桶的最值相减。（只是可能，但并不一定）。
比如下面这种情况：
-
上代码
public static int maxGap(int[] arr) {
if(arr == null || arr.length < 2) {
return 0;
}
// 只是给 最值 进行初始化，实际是想要数组中的数字
// 全局的最大最小值
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
int len = arr.length;
for(int i = 0; i < len; i++) {
max = Math.max(arr[i], max);
min = Math.min(arr[i], min);
}
if(max == min) {
return 0;
}
boolean bucketHasNum[] = new boolean[len+1]; // 每个桶是否装进来过数。缺省值全是 false
int bucketMax[] = new int[len+1]; // 每个桶当中的最大值
int bucketMin[] = new int[len+1]; // 每个桶当中的最小值
int bid = 0; // 第几号桶。 从0开始计数
for(int i = 0 ; i < len; i++) {
bid = bucket(arr[i], len, max, min);
bucketMax[bid] = bucketHasNum[bid] ? Math.max(arr[i], bucketMax[bid]) : arr[i];
bucketMin[bid] = bucketHasNum[bid] ? Math.min(arr[i], bucketMin[bid]) : arr[i];
bucketHasNum[bid] = true;
}
int res = 0; // 最大差值
int lastMax = bucketMax[0];
for(int i = 1 ; i <= len; i++) {
if(bucketHasNum[i]) {
res = Math.max(res, bucketMin[i] - lastMax); // 不能直接bucketMin【i】-bucketMax【i-1】，因为还有空桶
lastMax = bucketMax[i];
}
}
return res;
}
// 判断 一个数 要装入 第几号桶
public static int bucket(long num, long len, long max, long min) {
return (int)( (num-min) * len / (max-min) );
}
这块代码 bucket 这个功能耗了我基本一天的时间，搞不明白就很难受…
以下是我当下阶段的理解：
(图片中的最小值min为0)
这个数字 减去 最小值， 就是距最小值的距离。
第 i 号桶 乘 区间长度len 就是 代表这个桶中装入的数字范围。（因为是计算机中的除法。 ）
京公网安备 11010502036488号