最大间距

🎯 问题描述（来源于LeetCode）

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

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

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 109

示例：

  • 示例 1：
1
2
3
输入:nums = [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
  • 示例 2：
1
2
3
输入: nums = [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。

💻 解题思路

思路1：桶排序

思路1：代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return 0
        
        # 找到最小值和最大值
        min_val, max_val = min(nums), max(nums)
        if min_val == max_val:
            return 0
        
        n = len(nums)
        # 桶的大小至少为1
        bucket_size = max(1, (max_val - min_val) // (n - 1))
        # 桶的数量
        bucket_count = (max_val - min_val) // bucket_size + 1
        
        # 初始化桶，每个桶记录最小值和最大值
        buckets = [[float('inf'), float('-inf')] for _ in range(bucket_count)]
        
        # 将数字分配到桶中
        for num in nums:
            bucket_idx = (num - min_val) // bucket_size
            buckets[bucket_idx][0] = min(buckets[bucket_idx][0], num)
            buckets[bucket_idx][1] = max(buckets[bucket_idx][1], num)
        
        # 计算最大间距
        max_gap = 0
        prev_max = None
        
        for i in range(bucket_count):
            # 跳过空桶
            if buckets[i][0] == float('inf'):
                continue
                
            if prev_max is not None:
                max_gap = max(max_gap, buckets[i][0] - prev_max)
            
            prev_max = buckets[i][1]
        
        return max_gap

思路1：📊 性能分析

提交结果
  • 运行时间：623ms击败19.29%
  • 内存消耗：41.55MB击败5.17%
复杂度验证
  • 时间复杂度：O(N)O(N)
  • 空间复杂度：O(N)O(N)

思考