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(所有测试用例通过)总结最大间距问题展示了桶排序和鸽巢原理的应用。通过合理设置桶大小利用鸽巢原理保证最大间距只出现在非空桶之间实现了线性时间复杂度的排序。
