最大间距

难度：困难
给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。

如果数组元素个数小于 2，则返回 0。

示例 1:

输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。

示例 2:

输入: [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。

说明:

你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。
请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-gap

很朴素的思想就是排序，但是一般排序的时间复杂度都是O(nlogn)，这里我们可以用基数排序和桶排序

基数排序

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int size = nums.size();
        if(size < 2)
            return 0;
        vector<int> buf(size);
        int maxNum = *max_element(nums.begin(), nums.end());
        int exp = 1;
        while(maxNum >= exp){
            vector<int> cnt(10, 0);
            for(int iter : nums){
                int digit = (iter / exp) % 10;
                cnt[digit]++;
            }
            for(int i = 1; i < 10; i++)
                cnt[i] += cnt[i - 1];
            for(int i = size - 1; i >= 0; i--){
                int digit = (nums[i] / exp) % 10;
                buf[--cnt[digit]] = nums[i];
            }
            copy(buf.begin(), buf.end(), nums.begin());
            exp *= 10;
        }
        int ans = 0;
        for(int i = 1; i < size; i++)
            ans = max(ans, nums[i] - nums[i - 1]);
        return ans;
    }
};

桶排序

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int size = nums.size();
        if(size < 2)
            return 0;
        int minNum = *min_element(nums.begin(), nums.end());
        int maxNum = *max_element(nums.begin(), nums.end());
        int d = max(1, (maxNum - minNum) / (size - 1));
        int bucketSize = (maxNum - minNum) / d + 1;
        vector<pair<int, int>> bucket(bucketSize, {-1, -1});//记录最大值和最小值
        for(int iter : nums){
            int index = (iter - minNum) / d;
            if(bucket[index].first == -1)
                bucket[index] = {iter, iter};
            else{
                bucket[index].first = min(bucket[index].first, iter);
                bucket[index].second = max(bucket[index].second, iter);
            }
        }
        int res = 0;
        int pre = -1;
        for(int i = 0; i < bucketSize; i++){
            if(bucket[i].first == -1)   continue;
            if(pre != -1)
                res = max(res, bucket[i].first - bucket[pre].second);
            pre = i;
        }
        return res;
    }
};

主要是学习一下基数排序和桶排序

基数排序可以在 O(N)的时间内完成整数之间的排序。