牛客4582题解：桶排序算法求最大间隔详解

19339201706

一、问题描述

牛客4582题要求在一个未排序的整数数组中，找出排序后相邻元素的最大差值。题目要求时间复杂度为O(n)，空间复杂度为O(n)。

二、算法核心思想

采用桶排序的变种方法：

• 计算数组最小最大值
• 确定桶的大小和数量
• 将元素分配到各个桶中
• 记录每个桶的最大最小值
• 比较相邻非空桶的最小值与前一桶的最大值
  
  

三、完整代码实现（带注释）

1. #include <iostream>
   
2. #include <vector>
   
3. #include <climits>
   
4. #include <algorithm>
   
5. using namespace std;
   
6. 
   
7. int maximumGap(vector<int>& nums) {
   
8.     const int n = nums.size();
   
9.     if (n < 2) return 0;  // 边界条件处理
   
10. 
    
11.     // 获取数组最小最大值
    
12.     auto minmax = minmax_element(nums.begin(), nums.end());
    
13.     int min_val = *minmax.first, max_val = *minmax.second;
    
14. 
    
15.     // 计算桶大小和数量
    
16.     int bucket_size = max(1, (max_val - min_val) / (n - 1));
    
17.     int bucket_num = (max_val - min_val) / bucket_size + 1;
    
18. 
    
19.     // 初始化桶（只需记录每个桶的最大最小值）
    
20.     vector<pair<int, int>> buckets(bucket_num, {INT_MAX, INT_MIN});
    
21. 
    
22.     // 元素分桶
    
23.     for (int num : nums) {
    
24.         int idx = (num - min_val) / bucket_size;
    
25.         buckets[idx].first = min(buckets[idx].first, num);
    
26.         buckets[idx].second = max(buckets[idx].second, num);
    
27.     }
    
28. 
    
29.     // 计算最大间隔
    
30.     int max_gap = 0, prev_max = min_val;
    
31.     for (auto& bucket : buckets) {
    
32.         if (bucket.first == INT_MAX) continue;  // 跳过空桶
    
33.         max_gap = max(max_gap, bucket.first - prev_max);
    
34.         prev_max = bucket.second;
    
35.     }
    
36. 
    
37.     return max_gap;
    
38. }
    
39. 
    
40. int main() {
    
41.     int n, a;
    
42.     vector<int> test1;
    
43.     while (cin >> n) {
    
44.         test1.clear();
    
45.         for (int i = 0; i < n; i++) {
    
46.             cin >> a;
    
47.             test1.push_back(a);
    
48.         }
    
49.         cout << maximumGap(test1) << endl;
    
50.     }
    
51.     return 0;
    
52. }

复制代码

四、关键点解析

• 桶大小计算：
  
  
  • 确保至少有一个元素在桶中
  • 公式：max(1, (max_val - min_val)/(n-1))
    
    
• 桶数量确定：
  
  
  • 根据数据范围动态调整
  • 公式：(max_val - min_val)/bucket_size + 1
    
    
• 空桶处理：
  
  
  • 跳过没有元素的桶
  • 确保只比较有数据的相邻桶
    
    

五、扩展思考

• 如何处理浮点数数组？
• 如果数据分布极不均匀如何优化？
• 如何扩展到多维数据？
• 如何并行化这个算法？
  
  

来源：牛客4582题解：桶排序算法求最大间隔详解