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

一、问题描述

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

二、算法核心思想

采用桶排序的变种方法：

1. 计算数组最小最大值

2. 确定桶的大小和数量

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;  // 边界条件处理

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

    // 计算桶大小和数量
    int bucket_size = max(1, (max_val - min_val) / (n - 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, 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;
}

四、关键点解析

1. 桶大小计算：

• 确保至少有一个元素在桶中

• 公式：max(1, (max_val - min_val)/(n-1))

2. 桶数量确定：

• 根据数据范围动态调整

• 公式：(max_val - min_val)/bucket_size + 1

3. 空桶处理：

• 跳过没有元素的桶

• 确保只比较有数据的相邻桶

五、扩展思考

1. 如何处理浮点数数组？

2. 如果数据分布极不均匀如何优化？

3. 如何扩展到多维数据？

4. 如何并行化这个算法？