当前位置：首页 > 牛客 > 牛客4582题解法：桶排序优化求解最大间隔问题（附代码详解）

牛客4582题解法：桶排序优化求解最大间隔问题（附代码详解）

23小时前

一、题目解读

牛客4582题要求给定一个整数数组，求解数组中任意两个元素之间的最大间隔。题目核心在于高效计算元素间差异的最大值，传统暴力解法（O(n²)）在数据量增大时效率低下，因此需探索更优的算法策略。

二、解题思路

桶排序（Bucket Sort）思想，将元素分布映射到固定大小的桶中，通过桶的划分间接计算间隔。关键在于：

1. 利用数组最小最大值动态计算桶大小，保证每个桶代表近似等距区间；

2. 通过分桶后桶内极值更新，跳过空桶直接比较相邻桶边界，避免全局遍历；

3. 时间复杂度降至O(n)，适用于大规模数据场景。

三、解题步骤详解

1. 边界处理：当数组元素少于2个时，直接返回0；

2. 极值获取：通过minmax_element快速定位最小/最大值；

3. 桶参数计算：根据元素范围与数量动态确定桶大小（避免过小或过大）；

4. 分桶操作：将每个元素映射到对应桶，更新桶内最小/最大值；

5. 间隔计算：遍历非空桶，利用前一个桶的最大值与本桶最小值计算当前间隔，更新全局最大值。

四、代码与注释

#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;  // 边界条件：元素少于2个时返回0

   // 获取数组最小最大值
   auto minmax = minmax_element(nums.begin(), nums.end());
   int min_val = *minmax.first, max_val = *minmax.second;

   // 计算桶大小（确保非0且合理分布）
   int bucket_size = max(1, (max_val - min_val) / (n - 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, 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;
}