桶排序算法实战：牛客4493题最大间隔问题详解

19339201706

一、问题背景与算法思路

本题要求在一个无序数组中找到排序后相邻元素的最大差值。直接排序后遍历的时间复杂度为O(nlogn)，而题目要求O(n)时间复杂度。我们采用桶排序的变种算法，通过巧妙的分桶策略来优化计算。

二、完整代码实现（带详细注释）

1. class MaxDivision { public: int maxGap(vector& nums) { if (nums.size() < 2) return 0; // 边界条件处理
   
2.     // 找出数组中的最小值和最大值
   
3.     int min_val = *min_element(nums.begin(), nums.end());
   
4.     int max_val = *max_element(nums.begin(), nums.end());
   
5. 
   
6.     // 计算桶的大小和数量（关键步骤）
   
7.     int bucket_size = max(1, (max_val - min_val) / ((int)nums.size() - 1));
   
8.     int bucket_num = (max_val - min_val) / bucket_size + 1;
   
9. 
   
10.     // 初始化桶（存储每个桶的最小值和最大值）
    
11.     vector<pair<int, int>> buckets(bucket_num, {INT_MAX, INT_MIN});
    
12. 
    
13.     // 将元素放入桶中
    
14.     for (int num : nums) {
    
15.         int idx = (num - min_val) / bucket_size;  // 计算桶索引
    
16.         buckets[idx].first = min(buckets[idx].first, num);
    
17.         buckets[idx].second = max(buckets[idx].second, num);
    
18.     }
    
19. 
    
20.     // 计算最大间隔（关键步骤）
    
21.     int max_gap = 0;
    
22.     int prev_max = min_val;  // 前一个非空桶的最大值
    
23. 
    
24.     for (auto& bucket : buckets) {
    
25.         if (bucket.first == INT_MAX) continue; // 跳过空桶
    
26.         max_gap = max(max_gap, bucket.first - prev_max);
    
27.         prev_max = bucket.second;  // 更新前一个非空桶的最大值
    
28.     }
    
29. 
    
30.     return max_gap;
    
31. }
    
32. 
    
33. int findMaxDivision(vector<int> A, int n) {
    
34.     MaxDivision div;
    
35.     return div.maxGap(A);  // 接口适配函数
    
36. }
    
37. };

复制代码

三、关键算法要点

• 分桶策略：根据数组长度动态计算桶的大小和数量
• 桶内存储：每个桶只记录最小值和最大值
• 间隔计算：最大间隔一定出现在相邻非空桶之间
• 边界处理：处理空桶和最小/最大值的情况
  
  

四、复杂度分析

• 时间复杂度：O(n) （3次线性遍历）
• 空间复杂度：O(n) （桶的存储空间）
  
  

五、常见错误提醒

• 忘记处理数组长度小于2的情况
• 桶大小计算错误（必须至少为1）
• 没有正确处理空桶的情况
• 初始prev_max值设置错误
  
  

六、学习价值

通过本题可以掌握：

• 桶排序的变种应用
• 线性时间复杂度的排序相关问题解法
• 分桶策略的设计思路
• 极值问题的优化处理方法
  
  

来源：大矩学习资料