桶排序算法实战：牛客4493题最大间隔问题详解
一、问题背景与算法思路
本题要求在一个无序数组中找到排序后相邻元素的最大差值。直接排序后遍历的时间复杂度为O(nlogn)，而题目要求O(n)时间复杂度。我们采用桶排序的变种算法，通过巧妙的分桶策略来优化计算。
二、完整代码实现（带详细注释）
class MaxDivision { public: int maxGap(vector& nums) { if (nums.size() < 2) return 0; // 边界条件处理
// 找出数组中的最小值和最大值
int min_val = *min_element(nums.begin(), nums.end());
int max_val = *max_element(nums.begin(), nums.end());
// 计算桶的大小和数量（关键步骤）
int bucket_size = max(1, (max_val - min_val) / ((int)nums.size() - 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[idx].first = min(buckets[idx].first, num);
buckets[idx].second = max(buckets[idx].second, num);
}
// 计算最大间隔（关键步骤）
int max_gap = 0;
int 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 findMaxDivision(vector<int> A, int n) {
MaxDivision div;
return div.maxGap(A); // 接口适配函数
}
};三、关键算法要点
分桶策略：根据数组长度动态计算桶的大小和数量
桶内存储：每个桶只记录最小值和最大值
间隔计算：最大间隔一定出现在相邻非空桶之间
边界处理：处理空桶和最小/最大值的情况
四、复杂度分析
时间复杂度：O(n) （3次线性遍历）
空间复杂度：O(n) （桶的存储空间）
五、常见错误提醒
忘记处理数组长度小于2的情况
桶大小计算错误（必须至少为1）
没有正确处理空桶的情况
初始prev_max值设置错误
六、学习价值
通过本题可以掌握：
桶排序的变种应用
线性时间复杂度的排序相关问题解法
分桶策略的设计思路
极值问题的优化处理方法
参考：牛客4493题解
原创内容 转载请注明出处
