问题描述

给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度O(N)
例子：
5,9,8,3,15
那么排序后的数，3,5,8,9,15，因此相邻最大差值为15-9=6

解题思路

由于时间复杂度要求为O(N)，因此快排，归并排序都不能使用了。这里我们需要借助桶排序的思想：

1）找出数组的最大值max和最小值min
2）将区间均等的划分为 N + 1份，即有N + 1个桶。由于只有N个数，那么必有一个桶为空桶
3）遍历数组，将所有数入桶，并记录每一个桶的max和min
4）不需要考虑桶内数的差值，因为它都不会大于空桶两边的桶的差值
5）遍历每一个桶，由于每个桶只存该区间的max和min，因此前桶的max和后桶的min必相邻。
依次比较每两非空桶，即后桶的min减去前桶的max 的差值，即可获得最大的差值

实现代码

  public static int maxGap(int[] nums) {
    if (nums == null || nums.length < 2) {
            return 0;
        }
    // 1）找出数组的最大值max和最小值min
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for(int i = 0; i < nums.length; i++) {
      if (nums[i] > max) {
        max = nums[i];
      }
      if (nums[i] < min) {
        min = nums[i];
      }
    }
    // 区间内数字全相等
    if (min == max) {
      return 0;
    }
    // 2）将区间均等的划分为 N + 1份，即有N + 1个桶
    // 3）遍历数组，将所有数入桶，并记录每一个桶的max和min
    int len = nums.length;
    boolean[] hasNum = new boolean[len + 1];
    int[] maxNums = new int[len + 1];
    int[] minNums = new int[len + 1];
    int bid = 0;
    for(int i = 0; i < len; i++) {
      bid = getBucketId(max, min, len, nums[i]);
      maxNums[bid] = hasNum[i] ? Math.max(maxNums[bid], nums[i]) : nums[i];
      minNums[bid] = hasNum[i] ? Math.min(minNums[bid], nums[i]) : nums[i];
      hasNum[bid] = true;
    }
    int res = 0;
    int lastMax = maxNums[0];
    // 4）不需要考虑桶内数的差值，因为它都不会大于空桶两边的桶的差值
    // 遍历每一个桶，由于每个桶只存该区间的max和min，因此前桶的max和后桶的min必相邻。
    // 依次比较每两非空桶，即后桶的min减去前桶的max 的差值，即可获得最大的差值
    for(int i = 0; i <= len; i++) {
      if (hasNum[i]) {
        res = Math.max(res, minNums[i] - lastMax);
                lastMax = maxNums[i];
      }
    }
    return res;
  }

  /// max最大值，min最小值，划分多少等分，num数值，返回num落在哪个区间的index
  /// long是为了防溢出
  public static int getBucketId(long max, long min, long len, long num) {
    // 计算num占了多少份区间
    // 一份为 (max - min) / len
    return (int)((num - min) * len / (max - min));
  }