LeetCode 164. 最大间距
题目描述
题意分析
将数组按升序排列后，求相邻两个元素之间的最大差值。相邻指排序之后的位置关系，不是原数组的相邻关系，也不是直接求最大值减最小值。
元素不足两个时返回零，重复值之间的间隔为零。题目要求线性时间、线性额外空间，因此不能依赖比较排序再扫描；只需找到最大间隔，不必实际得到完整排序结果。
解法：桶划分维护相邻非空桶
核心思路
[!blue]
设全局最小、最大值分别为
minValue、maxValue，跨度为range。排序后共有n - 1个相邻间隔，它们的和恰好等于跨度，因此最大间隔至少达到平均值range / (n - 1)；间隔是整数，所以也不小于这个平均值的向上取整。按数值范围划桶，桶宽取
bucketSize = max(1, range / (n - 1))，这里除法向下取整。两个数落在同一个桶中，它们的整数差最多为bucketSize - 1；桶宽又不超过上述最大间隔的下界，因此真正的最大间隔不可能出现在同一桶内部。只需保留每个非空桶的最小值和最大值，无需存放或排序桶内所有元素。桶编号随数值递增，按编号扫描时，当前非空桶的最小值与前一非空桶的最大值，恰好是一对跨桶相邻元素；中间的空桶没有元素，不会提供额外邻居。
桶下标是
(num - minValue) / bucketSize，桶数为range / bucketSize + 1，最后的加一用于容纳最大值所在的桶。另用used标记是否有元素，不能让默认的零值参与最小值比较，因为零本身也是合法输入。先处理不足两个元素或全部相等的情况，之后跨度为正、桶宽至少为一。扫描非空桶并比较两侧边界，就能覆盖全部可能产生最大差值的位置。
解题步骤
- 元素不足两个时返回零；否则扫描数组求全局最小、最大值，两者相等也返回零。
- 计算桶宽和覆盖整个值域所需的桶数，创建桶最小值、最大值及使用标记数组。
- 将每个数映射到对应桶。首次放入时同时设置该桶最小、最大值，后续仅更新两个边界。
- 从小到大扫描桶，空桶直接跳过；比较当前非空桶最小值与
previousMax，更新最大间隔。- 将
previousMax更新为当前桶最大值。它初始取全局最小值，使第一个非空桶只贡献零，不需要额外特判。
代码实现
class Solution {
public int maximumGap(int[] nums) {
int n = nums.length;
if (n < 2) {
return 0;
}
int minValue = nums[0];
int maxValue = nums[0];
for (int num : nums) {
minValue = Math.min(minValue, num);
maxValue = Math.max(maxValue, num);
}
if (minValue == maxValue) {
return 0;
}
int range = maxValue - minValue;
// 桶内整数差小于桶宽，不会产生需要寻找的最大间隔。
int bucketSize = Math.max(1, range / (n - 1));
int bucketCount = range / bucketSize + 1;
int[] bucketMin = new int[bucketCount];
int[] bucketMax = new int[bucketCount];
boolean[] used = new boolean[bucketCount];
for (int num : nums) {
int index = (num - minValue) / bucketSize;
if (!used[index]) {
bucketMin[index] = bucketMax[index] = num;
used[index] = true;
} else {
bucketMin[index] = Math.min(bucketMin[index], num);
bucketMax[index] = Math.max(bucketMax[index], num);
}
}
int answer = 0;
int previousMax = minValue;
for (int i = 0; i < bucketCount; i++) {
if (!used[i]) {
continue;
}
// 只比较相邻非空桶，空桶不改变前一个有效最大值。
answer = Math.max(answer, bucketMin[i] - previousMax);
previousMax = bucketMax[i];
}
return answer;
}
}
func maximumGap(nums []int) int {
n := len(nums)
if n < 2 {
return 0
}
minValue, maxValue := nums[0], nums[0]
for _, num := range nums {
if num < minValue {
minValue = num
}
if num > maxValue {
maxValue = num
}
}
if minValue == maxValue {
return 0
}
valueRange := maxValue - minValue
// 桶内整数差小于桶宽，不会产生需要寻找的最大间隔。
bucketSize := valueRange / (n - 1)
if bucketSize < 1 {
bucketSize = 1
}
bucketCount := valueRange/bucketSize + 1
bucketMin := make([]int, bucketCount)
bucketMax := make([]int, bucketCount)
used := make([]bool, bucketCount)
for _, num := range nums {
index := (num - minValue) / bucketSize
if !used[index] {
bucketMin[index], bucketMax[index] = num, num
used[index] = true
} else {
if num < bucketMin[index] {
bucketMin[index] = num
}
if num > bucketMax[index] {
bucketMax[index] = num
}
}
}
answer, previousMax := 0, minValue
for i := 0; i < bucketCount; i++ {
if !used[i] {
continue
}
// 只比较相邻非空桶，空桶不改变前一个有效最大值。
if gap := bucketMin[i] - previousMax; gap > answer {
answer = gap
}
previousMax = bucketMax[i]
}
return answer
}
复杂度分析
- 时间复杂度：$O(n)$，求最值、分桶、扫描桶各一遍，桶数为 $O(n)$。
- 空间复杂度：$O(n)$。若平均间隔小于一，桶宽为一，桶数不超过
n；否则向下取整后的桶宽大于平均间隔的一半，桶数小于2n。每桶只保存两个边界和一个使用标记。
关键点总结
[!green]
- 相邻间隔总和固定，平均值提供最大间隔的下界。
- 桶内最大差严格小于这一候选下界，才有依据舍弃桶内排序。
- 按值域有序排列的桶只需比较相邻非空桶的“前最大、后最小”。
- 桶宽既排除了桶内答案，也限制桶数为线性规模，这两点共同保证算法成立。
易错点总结
[!yellow]
- 直接计算全局最大值减最小值，得到的是整段跨度，不是排序后相邻元素的差。
- 没有提前处理
n < 2，平均间隔的分母可能为零；桶宽也必须至少为一。- 桶数漏加一，最大元素对应的桶下标可能超出数组范围。
- 默认用零初始化桶最小值却不区分空桶，正数桶可能错误保留一个不存在的零。
- 扫描到空桶仍更新前一桶信息，破坏相邻非空桶的实际边界。
- 用两个桶的最小值相减，或两个最大值相减，都不能表示排序后的跨桶相邻间隔。
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！