最大间距

最大间距问题为什么需要线性排序？

• 问题: 求排序后相邻元素差值的最大值;
• 用比较排序需要 O(n log n), 且必须先真正排序;
• 若要求线性时间, 只能使用非比较排序 (桶排序、基数排序、计数排序);
• 本题输入为正整数, 桶排序与基数排序都适用;

最大间距如何实现？

function maximumGap(nums: number[]): number {
  if (nums.length < 2) return 0;

  const k = Math.floor(nums.length / 3);
  const buckets: number[][] = Array.from({ length: k + 1 }, () => []);
  const min = Math.min(...nums);
  const range = Math.max(...nums) - min;
  if (range === 0) return 0;
  for (const num of nums) {
    buckets[Math.floor(((num - min) / range) * k)].push(num);
  }

  const sorted: number[] = [];
  for (const bucket of buckets) {
    sorted.push(...bucket.sort((a, b) => a - b));
  }

  let res = 0;
  for (let i = 1; i < sorted.length; i++) {
    res = Math.max(res, sorted[i] - sorted[i - 1]);
  }
  return res;
}

最大间距的复杂度是多少？

• 时间复杂度: O(n), 桶数与元素数同阶, 一次线性扫描求相邻差;
• 空间复杂度: O(n), 桶与排序结果;