0164. Maximum Gap¶
题目信息¶
- 题号:
最大间距
- 难度:
Medium
- 主题:
数组、桶、鸽巢原理
- 原题:
- 重点:
从排序后的相邻关系,推导到只保存桶内极值并在线性时间比较跨桶间距
题目重述¶
给定非负整数数组 nums。将数组按升序排列后,返回相邻元素之间的最大差值;若数组
少于两个元素,则返回 0。
要求在线性时间、线性额外空间内完成。也就是说,直接使用时间为 O(n log n) 的
比较排序只能作为理解题意的基线,不能作为最终方案。
自建示例¶
输入:nums = [2,20,6,7]
输出:13
排序后为 [2,6,7,20],相邻差值为 4、1、13。
输入:nums = [5,5,5]
输出:0
数值范围宽度为 0,所有相邻差值都是 0。
输入:nums = [9]
输出:0
不存在一对相邻元素。
C++ 实现¶
#include <algorithm>
#include <limits>
#include <vector>
class Solution {
private:
int sortingBaseline(std::vector<int> nums) {
if (nums.size() < 2) {
return 0;
}
std::sort(nums.begin(), nums.end());
int largest_gap = 0;
for (int i = 1; i < static_cast<int>(nums.size()); ++i) {
largest_gap =
std::max(largest_gap, nums[i] - nums[i - 1]);
}
return largest_gap;
}
int bucketExtremes(const std::vector<int>& nums) {
int size = static_cast<int>(nums.size());
if (size < 2) {
return 0;
}
int minimum = *std::min_element(nums.begin(), nums.end());
int maximum = *std::max_element(nums.begin(), nums.end());
if (minimum == maximum) {
return 0;
}
long long range = static_cast<long long>(maximum) - minimum;
long long width = (range + size - 2) / (size - 1);
int bucket_count = static_cast<int>(range / width + 1);
std::vector<int> bucket_minimum(
bucket_count, std::numeric_limits<int>::max());
std::vector<int> bucket_maximum(
bucket_count, std::numeric_limits<int>::min());
std::vector<char> used(bucket_count, false);
for (int value : nums) {
int index = static_cast<int>(
(static_cast<long long>(value) - minimum) / width);
used[index] = true;
bucket_minimum[index] =
std::min(bucket_minimum[index], value);
bucket_maximum[index] =
std::max(bucket_maximum[index], value);
}
int largest_gap = 0;
int previous_maximum = minimum;
for (int index = 0; index < bucket_count; ++index) {
if (!used[index]) {
continue;
}
largest_gap = std::max(
largest_gap,
bucket_minimum[index] - previous_maximum);
previous_maximum = bucket_maximum[index];
}
return largest_gap;
}
public:
int maximumGap(std::vector<int>& nums) {
return bucketExtremes(nums);
}
};
题解¶
排序基线保留了什么信息¶
题目说的是“排序后相邻”,所以最自然的方案是先排序,再扫描相邻差值。
sortingBaseline 完整实现了这个定义,时间为 O(n log n)。它也揭示了真正需要的
信息:对每个数,只关心它在有序序列中的前驱,而不关心任意远距离数对。
线性要求使问题转变为:能否不恢复完整顺序,却仍找出某些相邻元素之间的最大空隙? 桶方案不会给每个元素排出名次,只保存若干数值区间里的最小值和最大值。
最大间距提供桶宽¶
设数组有 n 个数,最小值为 minimum,最大值为 maximum,数值跨度为
R = maximum - minimum。排序后有 n - 1 个相邻间距,它们的和是 R,
所以其中最大值至少为:
ceil(R / (n - 1))
将这个下界记为 width,并从 minimum 开始按宽度 width 划桶。整数落入
编号 (value - minimum) / width 的桶。同一桶覆盖的是一个半开数值段,其中任意
两个整数之差都小于 width;而全局最大间距至少为 width。因此全局最大间距
不可能由同一桶内的两个元素产生,它必然跨越两个非空桶。
这一步是从排序方案删除工作的关键:既然桶内不会产生答案,就不必知道桶内元素的顺序, 只需记住桶的最小值和最大值。
为什么只比较相邻非空桶¶
按桶编号从小到大扫描时,前一个非空桶中的所有数都不大于后一个非空桶中的所有数。 两桶边界处在完整排序结果中真正相邻的两个元素,必然是:
前一非空桶的最大值 -> 当前非空桶的最小值
空桶表示中间整段没有输入元素,应该直接跳过而不是把扫描断开。变量
previous_maximum 始终保存最近一个非空桶的最大值;遇到下一个非空桶时,用它的
bucket_minimum 计算跨桶间距,再更新状态。
首个非空桶包含全局最小值。代码把 previous_maximum 初始化为 minimum,
所以首桶产生的比较最多为桶内的 0 或较小差值,不影响答案,也避免为首桶另设分支。
具体走读¶
对 [2,20,6,7],n = 4、R = 18,因此
width = ceil(18 / 3) = 6:
桶 0:[2, 8) 已使用,minimum = 2,maximum = 7
桶 1:[8,14) 空
桶 2:[14,20) 空
桶 3:[20,26) 已使用,minimum = maximum = 20
桶 0 内的 2、6、7 不需要排序,因为其内部差值都小于 6。扫描跳过两个空桶后,比较
20 - 7 = 13,这正是排序后 7 与 20 的相邻间距。
若所有值相同,R = 0,最大间距直接为 0;这个分支也避免计算出宽度 0。若元素不足
两个,同样不存在相邻差值。range、桶宽计算和桶下标的减法使用 long long,
避免极端端点参与中间算术时溢出。
方案选择与复杂度¶
排序基线易于从定义验证,时间 O(n log n)、复制数组需要 O(n) 空间;桶方案用
两次线性扫描分别建立和读取桶,时间为 O(n)。由桶宽定义可得桶数不超过 n,
因此额外空间为 O(n)。题目明确要求线性时间,主解采用 bucketExtremes。