牛客4582题解：桶排序算法求最大间隔详解
https://dajuwangluo.cn/zb_users/upload/2025/07/202507111752235633266599.jpg一、问题描述牛客4582题要求在一个未排序的整数数组中，找出排序后相邻元素的最大差值。题目要求时间复杂度为O(n)，空间复杂度为O(n)。二、算法核心思想采用桶排序的变种方法：[*]计算数组最小最大值
[*]确定桶的大小和数量
[*]将元素分配到各个桶中
[*]记录每个桶的最大最小值
[*]比较相邻非空桶的最小值与前一桶的最大值
三、完整代码实现（带注释）
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
int maximumGap(vector<int>& nums) {
const int n = nums.size();
if (n < 2) return 0;// 边界条件处理
// 获取数组最小最大值
auto minmax = minmax_element(nums.begin(), nums.end());
int min_val = *minmax.first, max_val = *minmax.second;
// 计算桶大小和数量
int bucket_size = max(1, (max_val - min_val) / (n - 1));
int bucket_num = (max_val - min_val) / bucket_size + 1;
// 初始化桶（只需记录每个桶的最大最小值）
vector<pair<int, int>> buckets(bucket_num, {INT_MAX, INT_MIN});
// 元素分桶
for (int num : nums) {
int idx = (num - min_val) / bucket_size;
buckets.first = min(buckets.first, num);
buckets.second = max(buckets.second, num);
}
// 计算最大间隔
int max_gap = 0, prev_max = min_val;
for (auto& bucket : buckets) {
if (bucket.first == INT_MAX) continue;// 跳过空桶
max_gap = max(max_gap, bucket.first - prev_max);
prev_max = bucket.second;
}
return max_gap;
}
int main() {
int n, a;
vector<int> test1;
while (cin >> n) {
test1.clear();
for (int i = 0; i < n; i++) {
cin >> a;
test1.push_back(a);
}
cout << maximumGap(test1) << endl;
}
return 0;
}
四、关键点解析
[*]桶大小计算：
[*]确保至少有一个元素在桶中
[*]公式：max(1, (max_val - min_val)/(n-1))
[*]桶数量确定：
[*]根据数据范围动态调整
[*]公式：(max_val - min_val)/bucket_size + 1
[*]空桶处理：
[*]跳过没有元素的桶
[*]确保只比较有数据的相邻桶
五、扩展思考
[*]如何处理浮点数数组？
[*]如果数据分布极不均匀如何优化？
[*]如何扩展到多维数据？
[*]如何并行化这个算法？
来源：牛客4582题解：桶排序算法求最大间隔详解
页:
[1]