LeetCode 164. 最大间距
目录
题目描述
题意分析
给定一个未排序的非负整数数组，求把它排好序之后，相邻两个元素之间差值的最大值。数组元素少于两个时返回 0。
约束信号是本题唯一的难点来源：数组长度和元素值都可以到 $10^5$ 与 $10^9$ 量级，而进阶要求写死了「时间复杂度和空间复杂度都必须是线性的」。这句话等于直接禁掉了比较排序——任何基于比较的排序下界都是 $\Omega(n \log n)$，先排序再扫一遍虽然三行就能写完，但在面试里等于放弃了这道题。
换句话说，题目要的不是答案本身，而是「不完全排序也能拿到相邻最大差」的那条路径。注意问的是「排序后相邻元素的最大差」，不是任意两元素的最大差（那就是
max - min，一遍扫描的事），所以必须掌握元素在数轴上的分布结构。边界情况：长度为 0 或 1 返回 0；所有元素相同（此时
max - min == 0）；元素高度集中导致跨度小于元素个数；元素极度分散导致跨度远大于元素个数。
解法：桶划分维护相邻非空桶
核心思路
比较排序后再扫描虽然直观，但需要 $O(n \log n)$。题目要求线性时间，因此只保留求最大间距所需的信息：每个值域桶中的最小值和最大值。
设数组长度为
n，全局最小值、最大值分别为minValue、maxValue，值域跨度为range。排序后有n - 1个相邻间隔，它们的和是range，所以最大间隔至少是平均间隔。取桶宽：
bucketSize = max(1, range / (n - 1))同一桶覆盖连续的
bucketSize个整数，桶内任意两数之差最多为bucketSize - 1。当平均间隔至少为1时，有“桶内差 < 桶宽 ≤ 平均间隔 ≤ 答案”；当平均间隔小于1时，桶宽为1，同桶整数只能相等，而答案至少为1。因此答案一定出现在两个相邻非空桶之间。于是每个桶只记录最小值和最大值。按桶下标从小到大扫描，当前非空桶的最小值减去上一个非空桶的最大值，就是一组候选答案。空桶必须跳过，因为真正相邻的排序元素可能隔着多个空桶。
解题步骤
- 数组不足两个元素时返回
0；扫描得到全局最小值和最大值，二者相等时也返回0。- 根据平均间隔计算桶宽，并计算能覆盖
[minValue, maxValue]的桶数。- 将每个数放入对应桶。桶第一次使用时直接设置最小值和最大值，之后再更新两个边界。
- 从左到右扫描非空桶，用
当前桶最小值 - 前一非空桶最大值更新答案。- 例如
[3,6,9,1]的桶边界依次为[1]、[3]、[6]、空、[9]，跨桶间距为2、3、3，答案是3。
代码实现
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)$。平均间隔至少为
1时，桶宽大于平均间隔的一半，桶数少于2n；平均间隔小于1时，桶数不超过n。每个桶只保存常数个字段。
关键点总结
- 鸽巢原理给出下界：最大间距不小于平均间隔。
- 桶宽的选择保证桶内差严格小于候选最大间距，所以只需比较桶间边界。
- 桶内无需排序，只保存最小值和最大值。
- 扫描时比较的是相邻非空桶，不是相邻桶。
易错点总结
n < 2或minValue == maxValue未提前返回，会造成除零或无效分桶。- 桶宽可能因整数除法变成
0，必须至少取1。- 桶数漏掉
+ 1时，最大值对应的桶下标会越界。- 用当前桶最小值减前一个桶的最小值，或不跳过空桶，都会破坏跨桶边界的定义。
- 直接排序可以得到正确答案，但不满足题目要求的线性时间。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 912. 排序数组 | 中等 | 手写排序本体，可用基数排序验证非比较排序的线性性质 |
| 75. 颜色分类 | 中等 | 值域只有三种，一趟三路划分原地完成排序 |
| 274. H 指数 | 中等 | 用计数数组把值域截断在 n 内，绕开排序 |
| 347. 前 K 个高频元素 | 中等 | 以「出现次数」为桶下标，逆序取桶得到前 K 个 |
| 220. 存在重复元素 III | 困难 | 按 valueDiff 定桶宽，同桶必命中、邻桶需再验证 |
| 128. 最长连续序列 | 中等 | 同样是线性时间内提取顺序信息，改用哈希集合起点判定 |
| 41. 缺失的第一个正数 | 困难 | 值域受限时把下标当桶，原地归位省掉额外空间 |