5.6.1 一道奇葩的面试题
下面我来考查你一道算法题，有一个无序整型数组……
题目
有一个无序整型数组，如何求出该数组排序后的任意两个相邻元素的最大差值？要求时间和空间复杂度尽可能低。
可能题目有点绕，让我们来看一个例子。
哦，让我想想……
嗨，这还不简单吗？先使用时间复杂度为O（nlogn）的排序算法给原来的数组排序，然后遍历数组，对每两个相邻元素求差，最大差值不就出来了吗？
解法1：
使用任意一种时间复杂度为O（nlogn）的排序算法（如快速排序）给原数组排序，然后遍历排好序的数组，并对每两个相邻元素求差，最终得到最大差值。
该解法的时间复杂度是O（nlogn），在不改变原数组的情况下，空间复杂度是O(n)。
唉，我出这样的题目，显然不是为了让你来排序的。你再想想，有没有更快的解法？
没有了呀。不排序的话还能怎么做呢？
呵呵，那你回家等通知去吧！
5.6.2 解题思路
小灰，你刚刚去面试了？结果怎么样？
唉……
大黄，我今天遇见一道怪题，怎样才能计算出无序数组排序后的最大相邻差值？
嗯……这道题确实很有意思。虽然对数组排序以后肯定能得到正确的结果，但我们没有必要真的去进行排序。
不排序的话，该怎么办呢？
小灰，你记不记得，有哪些排序算法的时间复杂度是线性的？
好像有计数排序、桶排序，还有个什么基数排序……可你刚才不是说不用排序吗？
别着急，我们仅仅是借助一下这些排序的思想而已。小灰你想一下，这道题能不能像计数排序一样，利用数组下标来解决？
像计数排序一样？让我想想啊……
有了！我可以使用计数排序的思想，先找出原数组最大值和最小值的差……
解法2：
1. 利用计数排序的思想，先求出原数组的最大值max与最小值min的区间长度k（k=max-min+1），以及偏移量d=min。
2. 创建一个长度为k的新数组Array。
3. 遍历原数组，每遍历一个元素，就把新数组Array对应下标的值+1。例如原数组元素的值为n，则将Array[n-min]的值加1。遍历结束后，Array的一部分元素值变成了1或更高的数值，一部分元素值仍然是0。
4. 遍历新数组Array，统计出Array中最大连续出现0值的次数+1，即为相邻元素最大差值。
例如给定一个无序数组 { 2, 6, 3, 4, 5, 10, 9 }，处理过程如下图。
第1步，确定k（数组长度）和d（偏移量）。
第2步，创建数组。
第3步，遍历原数组，对号入座。
第4步，判断0值最多连续出现的次数，计算出最大相邻差。
很好，我们已经进步了很多。这个思路在数组元素差值不很悬殊的时候，确实效率很高。
可是设想一下，如果原数组只有3个元素：1、2、1 000 000，那就要创建长度是1 000 000的数组！想一想还能如何优化？
让我想想啊……
对了！桶排序的思想正好解决了这个问题！
解法3：
1. 利用桶排序的思想，根据原数组的长度n，创建出n个桶，每一个桶代表一个区间范围。其中第1个桶从原数组的最小值min开始，区间跨度是（max-min）/（n-1）。
2. 遍历原数组，把原数组每一个元素插入到对应的桶中，记录每一个桶的最大和最小值。
3. 遍历所有的桶，统计出每一个桶的最大值，和这个桶右侧非空桶的最小值的差，数值最大的差即为原数组排序后的相邻最大差值。
例如给出一个无序数组 { 2, 6, 3, 4, 5, 10, 9 }，处理过程如下图。
第1步，根据原数组，创建桶，确定每个桶的区间范围。
第2步，遍历原数组，确定每个桶内的最大和最小值。
第3步，遍历所有的桶，找出最大相邻差。
这个方法不需要像标准桶排序那样给每一个桶内部进行排序，只需要记录桶内的最大和最小值即可，所以时间复杂度稳定在O(n) 。
很好，让我们来写一下代码吧。
好的，我试试。
1. public static int getMaxSortedDistance(int[] array){
2.
3. //1.得到数列的最大值和最小值
4. int max = array[0];
5. int min = array[0];
6. for(int i=1; i
7. if(array[i] > max) {
8. max = array[i];
9. }
10. if(array[i] < min) {
11. min = array[i];
12. }
13. }
14. int d = max - min;
15. //如果max 和min 相等，说明数组所有元素都相等，返回0
16. if(d == 0){
17. return 0;
18. }
19.
20. //2.初始化桶
21. int bucketNum = array.length;
22. Bucket[] buckets = new Bucket[bucketNum];
23. for(int i = 0; i < bucketNum; i++){
24. buckets[i] = new Bucket();
25. }
26.
27. //3.遍历原始数组，确定每个桶的最大最小值
28. for(int i = 0; i < array.length; i++){
29. //确定数组元素所归属的桶下标
30. int index = ((array[i] - min) * (bucketNum-1) / d);
31. if(buckets[index].min==null || buckets[index].
min>array[i]){
32. buckets[index].min = array[i];
33. }
34. if(buckets[index].max==null || buckets[index].
max
35. buckets[index].max = array[i];
36. }
37. }
38.
39. //4.遍历桶，找到最大差值
40. int leftMax = buckets[0].max;
41. int maxDistance = 0;
42. for (int i=1; i
43. if (buckets[i].min == null) {
44. continue;
45. }
46. if (buckets[i].min - leftMax > maxDistance) {
47. maxDistance = buckets[i].min - leftMax;
48. }
49. leftMax = buckets[i].max;
50. }
51.
52. return maxDistance;
53. }
54.
55. /**
56. * 桶
57. */
58. private static class Bucket {
59. Integer min;
60. Integer max;
61. }
62.
63. public static void main(String[] args) {
64. int[] array = new int[] {2,6,3,4,5,10,9};
65. System.out.println(getMaxSortedDistance(array));
66. }
代码的前几步都比较直观，唯独第4步稍微有些不好理解：使用临时变量leftMax，在每一轮迭代时存储当前左侧桶的最大值。而两个桶之间的差值，则是buckets[i].minleftMax。
没错，这就是这道题目的最优解决方法。关于无序数组排序后最大差值的问题就介绍到这里，咱们下一节再见！