牛客4493题解析：桶排序优化求解最大间隔问题（附代码详...

15303105423 · 发表于 2025-6-23 10:40:33

一、题目解读

牛客4493题要求在一个整数数组中寻找最大间隔，即数组中任意两个元素之间的最大差值。题目强调需要高效算法，尤其在处理大规模数据时仍需保持性能。理解题目核心在于如何快速定位元素间的最远距离，避免暴力枚举带来的高时间复杂度。

二、解题思路

采用“桶排序+分桶策略”的巧妙思路解决该问题。核心逻辑如下：

1. 缩小搜索范围：通过预处理找出数组的最小值（min_val）和最大值（max_val），将搜索空间限定在[min_val, max_val]区间内。

2. 动态分桶：根据元素数量n动态计算桶大小（bucket_size），确保每个桶覆盖的元素间距均匀，避免稀疏或过度拥挤。公式：bucket_size = max(1, (max_val - min_val) / (n - 1))，保证至少n-1个非空桶。

3. 利用桶边界信息：每个桶记录最小值和最大值，通过遍历桶边界计算全局最大间隔，巧妙避开对原始数组元素的二次遍历。

三、解题步骤

1. 边界判断：若数组长度<2，直接返回0（无间隔）。

2. 预处理：使用STL的min_element和max_element快速定位min_val和max_val。

3. 桶参数计算：按公式推导bucket_size和桶数量bucket_num，确保分桶合理性。

4. 初始化桶：创建vector<pair<int, int>>存储每个桶的[min, max]区间，初始值设为INT_MAX和INT_MIN。

5. 元素分桶：遍历数组，根据(num - min_val) / bucket_size计算索引，更新对应桶的边界。

6. 计算最大间隔：

跳过空桶（first=INT_MAX）。

利用当前桶最小值与上一桶最大值（prev_max）的差值更新max_gap。

迭代中维护prev_max为当前桶最大值。

7. 返回结果：最终max_gap即为全局最大间隔。

四、代码和注释

class MaxDivision {
public:
int maxGap(vector<int>& 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;
// 初始化桶（记录每个桶的[min, max]）
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); // 当前桶min与上一桶max的差
prev_max = bucket.second; // 更新前驱max
}
return max_gap;
}
int findMaxDivision(vector<int> A, int n) {
MaxDivision div;
return div.maxGap(A);
}
};

复制代码

五、总结

该解法通过桶排序将线性时间复杂度降至O(n)，空间复杂度O(n)。关键在于通过动态分桶将全局搜索转化为局部区间比较，有效避免了对原始数据的二次遍历。此外，代码利用STL函数和INT_MAX/INT_MIN初始化技巧，既提升代码简洁性，又保障了极端情况下的正确性。对同类“区间最值问题”具有通用优化价值。

链接：桶排序