164. Maximum Gap（最大间距）

题目

LeetCode中文站

解答

根据题意我们就可以直到这是一题先排序，然后再寻找最大间距的题目，我们先使用最简单的解法试试。

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        if (nums.size() < 2) {
            return 0;
        }
        int maxGap = 0;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() - 1; i++) {
            maxGap = max(nums[i + 1] - nums[i], maxGap);
        }
        return maxGap;
    }
};

以上代码时间复杂度为，空间复杂度我们可以默认他为快速排序为。

现在就来继续优化上面的代码，之前我们在零基础学排序中学到，还有三种线性的时间复杂度的排序算法，桶排序、基数排序、计数排序，三种排序的应用场景有限。
但是在题目中提到你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。，所以根据这个条件，我们使用桶排序和基数排序是都合理的。

桶排序

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        if (nums.size() < 2) {
            return 0;
        }
        // 先找出最大和最小值
        int minNum = nums.front();
        int maxNum = nums.front();
        for (int i = 0; i < nums.size(); i++) {
            minNum = min(minNum, nums[i]);
            maxNum = max(maxNum, nums[i]);
        }
        
        // 先确定桶大小
        int bucketSize = max(1, (maxNum - minNum) / ((int)nums.size() - 1));
        int bucketCount = ceil((maxNum - minNum + 1) / (float)bucketSize);
        vector<vector<int>> bucket(bucketCount);
        
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == maxNum) {
                bucket.back().push_back(nums[i]);
                continue;
            }
            // 看数据是在n哪个桶中的
            int bucketIndex = (nums[i] - minNum) / bucketSize;
            bucket[bucketIndex].push_back(nums[i]);
        }
    
        nums.resize(0);
        for (int i = 0; i < bucket.size(); i++) {
            // 计算大小
            if (!bucket[i].empty()) {
                sort(bucket[i].begin(), bucket[i].end());
                nums.insert(nums.end(), bucket[i].begin(), bucket[i].end());
            }
        }
        
        int maxGap = 0;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() - 1; i++) {
            maxGap = max(nums[i + 1] - nums[i], maxGap);
        }
        return maxGap;
    }
};

以上代码的时间复杂度为，空间复杂度为。

基数排序

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        if (nums.size() < 2) {
            return 0;
        }
        // 先找出最大
        int maxNum = nums.front();
        for (int i = 0; i < nums.size(); i++) {
            maxNum = max(maxNum, nums[i]);
        }
        
        // 计算位数
        int bit = 0;
        while (1) {
            if (maxNum >= pow(10, bit)) {
                bit++;
            } else {
                break;
            }
        }
        
        
        for (int i = 0; i < bit; i++) {
            vector<vector<int>> bucket(10);
            // 从最低位开始排序
            for (auto subNum : nums) {
                int bitNum = int(subNum / pow(10, i)) % 10;
                bucket[bitNum].push_back(subNum);
            }
            // 重新放入桶中
            nums.resize(0);
            for (auto ve : bucket) {
                nums.insert(nums.end(), ve.begin(), ve.end());
            }
        }

        int maxGap = 0;
        for (int i = 0; i < nums.size() - 1; i++) {
            maxGap = max(nums[i + 1] - nums[i], maxGap);
        }
        return maxGap;
    }
};

以上代码的时间复杂度为，空间复杂度为。

当我AC的时候我发现了一个排名第一的答案，这个AC解很奇怪，他直接跳过了排序的步骤，通过桶的概念，把最大最小值存在来，最后通过比较找到了最大间距。这个解法我感觉我很厉害，但是我还没有找到一种很好的解释，所以我就先放着，希望知道的朋友可以告诉我一下，这个解法的原理是什么？

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        if(nums.size() < 2) {
            return 0;
        }
        int minval = INT_MAX;
        int maxval = INT_MIN;
        for(auto subnum : nums) {
            minval = min(subnum, minval);
            maxval = max(subnum, maxval);
        }
        
        int bucketSize = max(1, (maxval - minval) / ((int)nums.size() - 1));
        int bucketNum = (maxval - minval) / bucketSize;
        
        vector<int> bucketsMin(bucketNum, INT_MAX);
        vector<int> bucketsMax(bucketNum, INT_MIN);
        
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] == maxval || nums[i] == minval) {
                continue;
            }
            int index = (nums[i] - minval) / bucketSize;
            bucketsMin[index] = min(bucketsMin[index], nums[i]);
            bucketsMax[index] = max(bucketsMax[index], nums[i]);
        }
        int maxGap = 0;
        int pre = minval;
        for(int i = 0; i < bucketNum; i++) {
            if(bucketsMin[i] == INT_MAX || bucketsMax[i] == INT_MIN) {
                continue;
            }
            maxGap = max(maxGap, bucketsMin[i] - pre);
            pre = bucketsMax[i];
        }
        maxGap = max(maxGap, maxval - pre);
        return maxGap;
    }
};

以上代码的时间复杂度为，空间复杂度为。