LeetCode 第164题：最大间距

题目描述

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

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

难度

困难

题目链接

点击在LeetCode中查看题目

示例

示例 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

解题思路

方法：桶排序

为了满足线性时间和线性空间的要求，我们不能使用基于比较的排序算法。可以使用桶排序或基数排序。这里我们使用桶排序的思想。关键点：

计算数组的最大值和最小值
根据数组长度n，创建n-1个桶
每个桶记录落在该桶的最大值和最小值
计算相邻非空桶之间的差值（前一个桶的最大值和后一个桶的最小值之差）
返回最大的差值

时间复杂度：O(n)，其中n是数组长度。空间复杂度：O(n)，需要额外的桶空间。

代码实现

C# 实现

public class Solution {
    public int MaximumGap(int[] nums) {
        int n = nums.Length;
        if (n < 2) return 0;
        
        // 寻找最大值和最小值
        int minVal = nums[0];
        int maxVal = nums[0];
        foreach (int num in nums) {
            minVal = Math.Min(minVal, num);
            maxVal = Math.Max(maxVal, num);
        }
        
        // 如果最大值等于最小值，则所有元素相同，最大间距为0
        if (maxVal == minVal) return 0;
        
        // 每个桶的大小
        int bucketSize = Math.Max(1, (maxVal - minVal) / (n - 1));
        // 桶的数量
        int bucketCount = (maxVal - minVal) / bucketSize + 1;
        
        // 创建桶，每个桶记录最大值和最小值
        int?[] minBucket = new int?[bucketCount];
        int?[] maxBucket = new int?[bucketCount];
        
        // 将元素放入桶中
        foreach (int num in nums) {
            int idx = (num - minVal) / bucketSize;
            minBucket[idx] = minBucket[idx] == null ? num : Math.Min(minBucket[idx].Value, num);
            maxBucket[idx] = maxBucket[idx] == null ? num : Math.Max(maxBucket[idx].Value, num);
        }
        
        // 计算相邻非空桶之间的最大差值
        int maxGap = 0;
        int prevMax = maxBucket[0].Value;
        
        for (int i = 1; i < bucketCount; i++) {
            // 跳过空桶
            if (minBucket[i] == null) continue;
            
            // 计算当前桶的最小值和前一个非空桶的最大值之差
            maxGap = Math.Max(maxGap, minBucket[i].Value - prevMax);
            prevMax = maxBucket[i].Value;
        }
        
        return maxGap;
    }
}

Python 实现

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)
        
        # 如果最大值等于最小值，则所有元素相同，最大间距为0
        if max_val == min_val:
            return 0
        
        # 每个桶的大小
        bucket_size = max(1, (max_val - min_val) // (n - 1))
        # 桶的数量
        bucket_count = (max_val - min_val) // bucket_size + 1
        
        # 创建桶，每个桶记录最大值和最小值
        min_bucket = [None] * bucket_count
        max_bucket = [None] * bucket_count
        
        # 将元素放入桶中
        for num in nums:
            idx = (num - min_val) // bucket_size
            min_bucket[idx] = num if min_bucket[idx] is None else min(min_bucket[idx], num)
            max_bucket[idx] = num if max_bucket[idx] is None else max(max_bucket[idx], num)
        
        # 计算相邻非空桶之间的最大差值
        max_gap = 0
        prev_max = max_bucket[0]
        
        for i in range(1, bucket_count):
            # 跳过空桶
            if min_bucket[i] is None:
                continue
            
            # 计算当前桶的最小值和前一个非空桶的最大值之差
            max_gap = max(max_gap, min_bucket[i] - prev_max)
            prev_max = max_bucket[i]
            
        return max_gap

C++ 实现

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return 0;
        
        // 寻找最大值和最小值
        int minVal = *min_element(nums.begin(), nums.end());
        int maxVal = *max_element(nums.begin(), nums.end());
        
        // 如果最大值等于最小值，则所有元素相同，最大间距为0
        if (maxVal == minVal) return 0;
        
        // 每个桶的大小
        int bucketSize = max(1, (maxVal - minVal) / (n - 1));
        // 桶的数量
        int bucketCount = (maxVal - minVal) / bucketSize + 1;
        
        // 创建桶，每个桶记录最大值和最小值
        vector<pair<int, int>> buckets(bucketCount, {-1, -1}); // {min, max}
        
        // 将元素放入桶中
        for (int num : nums) {
            int idx = (num - minVal) / bucketSize;
            if (buckets[idx].first == -1) {
                buckets[idx].first = buckets[idx].second = num;
            } else {
                buckets[idx].first = min(buckets[idx].first, num);
                buckets[idx].second = max(buckets[idx].second, num);
            }
        }
        
        // 计算相邻非空桶之间的最大差值
        int maxGap = 0;
        int prevMax = buckets[0].second;
        
        for (int i = 1; i < bucketCount; i++) {
            // 跳过空桶
            if (buckets[i].first == -1) continue;
            
            // 计算当前桶的最小值和前一个非空桶的最大值之差
            maxGap = max(maxGap, buckets[i].first - prevMax);
            prevMax = buckets[i].second;
        }
        
        return maxGap;
    }
};

性能分析

各语言实现的性能对比：

实现语言	执行用时	内存消耗	特点
C#	140 ms	46.2 MB	实现清晰，性能适中
Python	1712 ms	26.4 MB	代码简洁，但性能较差
C++	132 ms	58.5 MB	性能最优