最大间距

题目

题目来源：力扣（LeetCode）

给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0。

示例 1:

输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。

示例 2:

输入: [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。

方法一：基数排序

题目范围是2的32次方以内，所以我们把数据看成是2的16次方也就是进制65536，这样只要做两次基数排序即可。这里需要注意题中要求，线性时间复杂度和空间复杂度。用计数排序来算，数据范围太大，因此不符合题目要求；线性排序，快排和归并排序的时间复杂度都是nlog(n)，只有用基数排序O(n) 满足条件，所以使用 基数排序。

基数排序

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。步骤：

1. 取得数组中的最大数，并取得最高位数；
2. count为桶数组，根据个位数的数值，遍历数组将它们分配至编号0到9的桶子中；
3. 将桶中的数值重新串接起来，通过buf数组暂存，并拷贝给原始数组；
4. 重复2,3步，依次类推直至最高位排序完成。

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumGap = function (nums) {
  const len = nums.length;
  if (len < 2) return 0;
  // 记录下标和
  let cnt = new Array(65536).fill(0);
  // 临时数组
  let temp = new Array(nums.length);
  for (let i = 0; i < nums.length; i++) {
    cnt[nums[i] & 0xffff] += 1;
  }
  // 每一个下标的前缀和
  for (let i = 1; i < 65536; i++) {
    cnt[i] += cnt[i - 1];
  }
  // 把数字按照记录的下标放到临时数组
  for (let i = nums.length - 1; i >= 0; i--) {
    temp[--cnt[nums[i] & 0xffff]] = nums[i];
  }
  // 重置
  cnt = new Array(65536).fill(0)
  for (let i = 0; i < temp.length; i++) {
    cnt[(temp[i] & 0xffff0000) >> 16] += 1;
  }
  for (let i = 1; i < 65536; i++) {
    cnt[i] += cnt[i - 1];
  }
  for (let i = nums.length - 1; i >= 0; i--) {
    nums[--cnt[(temp[i] & 0xffff0000) >> 16]] = temp[i];
  }
  let result = 0;
  for (let i = 1; i < nums.length; i++) {
    result = Math.max(result, nums[i] - nums[i - 1]);
  }
  return result;
};

方法二：桶排序

将数组按照最小间距分成若干个大小为 d 的桶，并找出每个整数所在的桶，元素之间的最大间距一定不会出现在某个桶的内部，而一定会出现在不同桶当中。
因此，在找出每个元素所在的桶之后，我们可以维护每个桶内元素的最大值与最小值。随后，只需从前到后不断比较相邻的桶，用后一个桶的最小值与前一个桶的最大值之差作为两个桶的间距，最终就能得到所求的答案。

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumGap = function (nums) {
  const n = nums.length;
  if (n < 2) {
    return 0;
  }
  // 找到最大值、最小值
  const minVal = Math.min(...nums);
  const maxVal = Math.max(...nums);
  // 求出每个桶的长度
  const d = Math.max(1, Math.floor(maxVal - minVal) / (n - 1));
  // 求出桶的数量，桶数量至少一个
  const bucketSize = Math.floor((maxVal - minVal) / d) + 1;
  // 只需要关注每个桶里的最大值和最小值，其他值不记录
  const bucket = new Array(bucketSize).fill(0).map(x => new Array(2).fill(0));
  for (let i = 0; i < bucketSize; ++i) {
    // 初始化全为 -1
    bucket[i].fill(-1);
  }
  // 入桶，每个桶只关心桶内的最大值和最小值
  for (let i = 0; i < n; i++) {
    // 求出该数属于哪一个桶
    const idx = Math.floor((nums[i] - minVal) / d);
    if (bucket[idx][0] === -1) { // 如果该桶没有数，则当前最大值和最小值均为该数
      bucket[idx][0] = bucket[idx][1] = nums[i];
    } else { // 比较大小，更新最大值和最小值
      bucket[idx][0] = Math.min(bucket[idx][0], nums[i]);
      bucket[idx][1] = Math.max(bucket[idx][1], nums[i]);
    }
  }
  // ret 记录最大间距
  let ret = 0;
  // prev记录前一个非空桶的编号
  let prev = -1;
  for (let i = 0; i < bucketSize; i++) {
    // 桶为空，则跳过
    if (bucket[i][0] == -1) {
      continue;
    }
    // 桶不为空
    if (prev != -1) {
      // 更新最大差值
      ret = Math.max(ret, bucket[i][0] - bucket[prev][1]);
    }
    // 更新桶的编号
    prev = i;
  }
  return ret;
};