算法刷题(3)：相邻两数的最大差值

题目：

给定一个数组，求如果排序之后，相邻两数的最大差值。要求时间复杂度O(N)，且要求不能用非基于比较的排序。

例子：

输入：[1，2，7，4]

输出：3

输入一个数组[1, 2, 7, 4]，排序之后为[1, 2, 4, 7]，那么输出相邻两数的最大差值为7-4=3.

解法：

首先，输入的数组是还没有排好序的，题目要求是不能使用非基于比较的排序而且排序算法的时间复杂度最低都要O(NlogN)，这不符合题目要求的时间复杂度O(N)，所以我们不能用普通的排序算法去解决该问题。要做到时间复杂度为O(N)，那么第一时间想到的就是遍历数组的时候只会对数组遍历一趟。

这里给大家介绍一种非常巧妙的算法解决该问题。

假如数组中有n个数，遍历一遍数组得到数组中的最大值max，最小值min，然后我们为这n个数准备n+1个桶来装这n个数。

如我们的输入数组中有9个数，遍历一遍数组后得到数组中的最小值min和最大值max.

1. 若min等于max，则说明数组中的这9个数都是一样的，那立马返回相邻两数的最大差值为0.

2. 若min不等于max，此刻假设min=0，max=99，然后因为数组有9个数，那桶的数目就为10个，min是第一个桶的最小值，max是最后一个桶的最大值.

然后再从头开始遍历数组，数组中的最小值一定进入0号桶，数组中的最大值一定进入9号桶，数组中的其他元素也依次进桶.

现在有一个很重要的结论，那就是，9个数，10个桶，遍历完一轮数组之后，其中第一个桶和最后一个桶一定不为空，而且，中间的桶必定至少有一个桶是空桶！

还是用上述提到的例子，假设每一个桶内的元素都是按从小到大排好序的，而且0~9号桶也是按从小到大排好序(1号桶里的元素比0号桶里的元素都大，2号桶里的元素比1号桶里的元素都大)，所以整个数组就可看成是排好序的。因为空桶的存在，相邻两数的最大差值有如下的情况。

1.桶内相邻两数的最大差值

可以看出，一个桶内的相邻最大差值最大也就可能是9-0=9.

2.桶间相邻两数的最大差值(中间无空桶)

可以看出，桶间相邻两数的最大差值(中间无空桶)的最大差值的范围是1~19.

3.桶间相邻两数的最大差值(中间有空桶)

可以看出，桶间相邻两数的最大差值(中间有空桶)的最大差值的范围是10~29.正是中间有空桶的存在，就完美排除掉了第1种情况(桶内相邻两数的最大差值)，也即，排好序的数组中的两数最大差值，那两个数绝对不可能在一个桶内！

所以，排序后数组的相邻两数最大差值出现的情况只可能是上面的情况2和情况3，因此只需要判断相邻两个桶的相邻两数的最大即可，也即把所有桶都遍历一遍，然后用该桶的最小值减去前一个非空桶的最大值(因为这样才是数组排序后的相邻两个数)，然后最后得出最大差值。

下面举一个例子来说明整个算法的流程。

输入一个数组[17, 0, 99, 23, 67, 13, 14, 89, 4]，因为这个数组有9个数，所以分配10个桶。

1. 先遍历整个数组，找出最小值min=0，最大值max=99.

2. 分配10个桶，编号为0~9.

3.遍历数组，依次入桶，记录每个桶的最小值和最大值.入桶的算法为

，num为当前值，Len为数组长度，得到的结果为该num应该入几号桶。

代码：

public class MaxGap {

  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;
  }

  public static int bucket(long num, long len, long min, long max) {
    return (int) ((num - min) * len / (max - min));

好了，今天的算法刷题到此为止讲述完毕，如果您对题目有更好的解法或者更好的想法，或者您对题目有什么疑惑或者我讲错的地方，又或者您有其他的有趣的题目想让我们讲解的，欢迎评论区留言告诉我们，我们一定进行回复，让我们共同交流共同进步！