写一个分割数组的最大差值使用c++

下面是一个使用 C++ 的分割数组的最大差值的示例代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int maxGap(vector<int>& nums) {
    if (nums.size() < 2) {
        return 0;
    }
    int n = nums.size();
    int minVal = *min_element(nums.begin(), nums.end());
    int maxVal = *max_element(nums.begin(), nums.end());
    if (minVal == maxVal) {
        return 0;
    }
    vector<bool> hasNum(n + 1, false);
    vector<int> minArr(n + 1, INT_MAX);
    vector<int> maxArr(n + 1, INT_MIN);
    for (int i = 0; i < n; ++i) {
        int bucket = (long long)(nums[i] - minVal) * n / (maxVal - minVal);
        minArr[bucket] = min(minArr[bucket], nums[i]);
        maxArr[bucket] = max(maxArr[bucket], nums[i]);
        hasNum[bucket] = true;
    }
    int res = 0;
    int lastMax = maxArr[0];
    for (int i = 1; i <= n; ++i) {
        if (hasNum[i]) {
            res = max(res, minArr[i] - lastMax);
            lastMax = maxArr[i];
        }
    }
    return res;
}

int main() {
    vector<int> nums = {1, 3, 2, 5, 4, 7, 6, 9, 8};
    cout << maxGap(nums) << endl; // 输出2
    return 0;
}

该算法的时间复杂度为 O(n)，使用桶排序的思想，先找出数组中的最小值和最大值，然后将整个区间 [minVal, maxVal] 等分为 n 个桶，每个桶的区间长度为 (maxVal - minVal) / n。对于每个数，将其放入对应的桶中，并更新该桶的最大值和最小值。最后遍历整个桶数组，计算相邻桶之间的最大差值，即可得到分割数组的最大差值。