0164. 最大间距【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 桌排序

1. 📝 题目描述

• leetcode

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

您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。

示例 1：

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

示例 2：

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

---

提示：

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9

2. 🎯 s.1 - 桌排序

c

int maximumGap(int* nums, int numsSize) {
    if (numsSize < 2) return 0;
    int minVal = nums[0], maxVal = nums[0];
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] < minVal) minVal = nums[i];
        if (nums[i] > maxVal) maxVal = nums[i];
    }
    if (minVal == maxVal) return 0;
    int bucketSize = (maxVal - minVal) / (numsSize - 1);
    if (bucketSize < 1) bucketSize = 1;
    int bucketCount = (maxVal - minVal) / bucketSize + 1;
    int* bucketsMin = (int*)malloc(sizeof(int) * bucketCount);
    int* bucketsMax = (int*)malloc(sizeof(int) * bucketCount);
    for (int i = 0; i < bucketCount; i++) {
        bucketsMin[i] = INT_MAX;
        bucketsMax[i] = INT_MIN;
    }
    for (int i = 0; i < numsSize; i++) {
        int idx = (nums[i] - minVal) / bucketSize;
        if (nums[i] < bucketsMin[idx]) bucketsMin[idx] = nums[i];
        if (nums[i] > bucketsMax[idx]) bucketsMax[idx] = nums[i];
    }
    int maxGap = 0, prevMax = bucketsMax[0];
    for (int i = 1; i < bucketCount; i++) {
        if (bucketsMin[i] == INT_MAX) continue;
        int gap = bucketsMin[i] - prevMax;
        if (gap > maxGap) maxGap = gap;
        prevMax = bucketsMax[i];
    }
    free(bucketsMin);
    free(bucketsMax);
    return maxGap;
}

js

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumGap = function (nums) {
  const n = nums.length
  if (n < 2) return 0
  let minVal = Math.min(...nums)
  let maxVal = Math.max(...nums)
  if (minVal === maxVal) return 0
  const bucketSize = Math.max(1, Math.floor((maxVal - minVal) / (n - 1)))
  const bucketCount = Math.floor((maxVal - minVal) / bucketSize) + 1
  const bucketsMin = new Array(bucketCount).fill(Infinity)
  const bucketsMax = new Array(bucketCount).fill(-Infinity)
  for (const num of nums) {
    const idx = Math.floor((num - minVal) / bucketSize)
    bucketsMin[idx] = Math.min(bucketsMin[idx], num)
    bucketsMax[idx] = Math.max(bucketsMax[idx], num)
  }
  let maxGap = 0,
    prevMax = bucketsMax[0]
  for (let i = 1; i < bucketCount; i++) {
    if (bucketsMin[i] === Infinity) continue
    maxGap = Math.max(maxGap, bucketsMin[i] - prevMax)
    prevMax = bucketsMax[i]
  }
  return maxGap
}

py

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return 0
        min_val, max_val = min(nums), max(nums)
        if min_val == max_val:
            return 0
        bucket_size = max(1, (max_val - min_val) // (n - 1))
        bucket_count = (max_val - min_val) // bucket_size + 1
        buckets_min = [float('inf')] * bucket_count
        buckets_max = [float('-inf')] * bucket_count
        for num in nums:
            idx = (num - min_val) // bucket_size
            buckets_min[idx] = min(buckets_min[idx], num)
            buckets_max[idx] = max(buckets_max[idx], num)
        max_gap = 0
        prev_max = buckets_max[0]
        for i in range(1, bucket_count):
            if buckets_min[i] == float('inf'):
                continue
            max_gap = max(max_gap, buckets_min[i] - prev_max)
            prev_max = buckets_max[i]
        return max_gap

• 时间复杂度：$O(n)$，其中 $n$ 是数组长度
• 空间复杂度：$O(n)$，桶数组的大小

算法思路：

• 根据鸽巢原理，最大间距不会小于 $\lceil (maxVal-minVal)/(n-1)\rceil$
• 将数组元素分配到等宽的桶中，每个桶只记录最大值和最小值
• 最大间距只可能出现在相邻非空桶之间（后一个桶的最小值 - 前一个桶的最大值）