[算法题] 求数组有序后相邻元素之间的最大差值
1. 题目要求
给定无序数组（此数组是long类型的数组，但以下示例只列一些小一点的数），例如：
3, 1, 12, 9, 3, 7, 1, 4, 7, 8, 10
求数组有序后相邻元素之间的最大差值，数组有序后如下：
1, 1, 3, 3, 4, 7, 7, 8, 9, 10, 12
可以发现数组有序后相邻元素之间的最大差值为3：
要求写一个算法实现此题目，且时间复杂度为O(n)
2. 题目分析
题目要求是求数组有序后相邻元素之间的最大差值，那么需要对数组进行排序吗？
8大经典排序排序算法中，时间复杂度最低的为桶排序，其时间复杂度为O(n)，但是由于数组是long类型的，其中的数可能很大，例如假设数组中只有3个数，100128124、12912312和8231，假如使用桶排序的话需要准备一个长度为100128124的额外数组用于排序（参考桶排序），这样显然太坑了吧。
于是我们考虑使用"桶排序"的思想来做这个题目，但是不对数组进行排序。
3. 实现思路
(1) 假设无序数组的长度为9，其中元素的取值范围为0, 49，即数组的最小值为0，最大值为49
(2) 准备10（数组长度+1）个"桶"，平分数组取值范围，即10个"桶"，假设编号为0~9，那么0号桶装的数字为0, 4，1号桶装的数字为4, 9，以此类推，9号桶装的数字的范围为45, 49
(3) 遍历数组，将每个元素装入对应的"桶"中
到这里后，我们可以得出以下重要的结论：
- 结论一：因为我们准备了 N+1 个桶，数组的长度为N，所以必然有>=1个桶是空桶，另外可以确定的是，最小值一定放在第一个桶中，最大值一定放在最后一个桶中，所以第一个桶和最后一个桶一定不是空桶。
- 结论二：一个空桶的左边的第一个非空桶中的最大值和它右边第一个非空桶中的最小值，在数组有序后一定是相邻的，例如2号桶是空桶，它左边的第一个非空桶是0号桶，0号桶的最大值为3,2号桶右边的第一个非空桶是3号桶，3号桶的最小值为17，在数组有序后，3和17一定是相邻的。
- 结论三：一个空桶的左边第一个非空桶中的最大值与它右边第一个非空桶中的最小值的差值一定大于这个空桶的取值范围的差值。于是我们发现，要求数组有序相邻元素之间的最大差值，不需要考虑桶内部的差值，桶内部的差值最大为4（示例中桶内部的最大差值），而由于有空桶的存在，所以数组有序后相邻元素之间的最大差值肯定是大于4的。于是我们发现，只要记录每个桶的最大值和最小值就可以得到最终的结果。
(4) 遍历所有的非空桶，记录前一个桶的最大值和后一个桶的最小值的差值，这些差值中的最大值就是我们题目的最终结果。
4. Java代码实现
public static int maxGap(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
int len = nums.length;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < len; i++) {
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]);
}
if (min == max) {
return 0;
}
boolean[] hasNum = new boolean[len + 1];
int[] maxs = new int[len + 1];
int[] mins = new int[len + 1];
int bid = 0;
for (int i = 0; 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;
}
int res = 0;
int lastMax = maxs[0];
int i = 1;
for (; i <= len; i++) {
if (hasNum[i]) {
res = Math.max(res, mins[i] - lastMax);
lastMax = maxs[i];
}
}
return res;
}
// 此方法用于计算num这个数应该进入哪个桶
// 返回桶的标号
public static int bucket(long num, long len, long min, long max) {
return (int) ((num - min) * len / (max - min));
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019.04.24 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
