LeetCode 164：最大间距 | 桶排序与鸽巢原理
LeetCode 164：最大间距 | 桶排序与鸽巢原理
引言
最大间距（Maximum Gap）是 LeetCode 第 164 题，难度为 Hard。题目要求在未排序的数组中找到排序后相邻元素之间的最大差值，要求使用线性时间复杂度和 O(n) 空间复杂度。
这道题不能使用简单的排序，因为要求线性时间。解决方案基于桶排序和鸽巢原理：首先找到最大值和最小值，确定桶的大小，然后使用桶来记录每个桶内的最小值和最大值。
问题分析
题目描述
给定未排序数组 nums，返回排序后相邻元素之间的最大差值。如果数组元素少于 2 个，返回 0。
问题特点
要求线性时间复杂度和 O(n) 空间复杂度，普通的排序算法（如快速排序）不满足要求。需要使用桶排序。
解决方案
桶排序方法
def maximumGap(nums): if len(nums) < 2: return 0 min_val = min(nums) max_val = max(nums) if min_val == max_val: return 0 bucket_size = (max_val - min_val) // (len(nums) - 1) if bucket_size == 0: bucket_size = 1 bucket_num = (max_val - min_val) // bucket_size + 1 buckets = [[float('inf'), float('-inf')] for _ in range(bucket_num)] for num in nums: idx = (num - min_val) // bucket_size buckets[idx][0] = min(buckets[idx][0], num) buckets[idx][1] = max(buckets[idx][1], num) max_gap = 0 previous_max = min_val for bucket_min, bucket_max in buckets: if bucket_min == float('inf'): continue max_gap = max(max_gap, bucket_min - previous_max) previous_max = bucket_max return max_gap算法详解
- 找到数组的最小值和最大值
- 计算桶大小：bucket_size = (max - min) / (n - 1)
- 将元素放入对应的桶中，记录每个桶的最小值和最大值
- 遍历所有桶，计算相邻非空桶的最大差值
鸽巢原理
根据鸽巢原理，n 个数放入 n-1 个桶后，至少有一个桶是空的。最大间距一定大于等于桶大小，且只可能出现在非空桶之间。
复杂度分析
时间复杂度
时间复杂度为 O(n)，因为只需要常数次遍历。
空间复杂度
空间复杂度为 O(n)，用于存储桶。
代码实现
Python 实现
def maximumGap(nums): if len(nums) < 2: return 0 min_val = min(nums) max_val = max(nums) if min_val == max_val: return 0 n = len(nums) 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: idx = (num - min_val) // bucket_size buckets[idx][0] = min(buckets[idx][0], num) buckets[idx][1] = max(buckets[idx][1], num) max_gap = 0 previous_max = min_val for bucket_min, bucket_max in buckets: if bucket_min == float('inf'): continue max_gap = max(max_gap, bucket_min - previous_max) previous_max = bucket_max return max_gap测试用例
def test_maximum_gap(): assert maximumGap([3, 6, 9, 1]) == 3 assert maximumGap([10]) == 0 assert maximumGap([1, 1, 1, 1]) == 0 assert maximumGap([1, 3, 6, 9]) == 3 print("所有测试用例通过！")总结
最大间距问题展示了桶排序和鸽巢原理的应用。通过合理设置桶大小，利用鸽巢原理保证最大间距只出现在非空桶之间，实现了线性时间复杂度的排序。