题目分析

本题的难点在于如何在线性的时间复杂度和空间复杂度下完成此题。

排序

最朴素的方法是将数组进行排序，然后遍历一次数组，求出最大间距

算法的**时间复杂度为$O(nlog(n))$，空间复杂度为$O(1)$**。

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

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

桶排序思想

上面的排序算法可以用其他的任意排序方法代替，相关的知识可以参考Leetcode912题相关博客。

这里直接介绍一种不用排序，只利用桶排序思想的一种解题技巧。

我们先明白一个数学原理，n个数，最大值为maxi，最小值为mini，且n个数都为整数，那么它们之间的最大间距至少为
$$\frac{maxi - mini}{n}$$

因此我们可以建立n + 1个桶，桶的间距为$\frac{maxi - mini}{n}$，多出的一个桶是保证边缘的安全性。那么间距最大的两个数一定位于两个不同的桶之中。这样每个桶就不需要存放所有的元素，只需要记录每个桶元素的最大值和最小值。那么间距一定是第m个桶的最大值和第n个桶的最小值之差，其中n>m，并且n和m之间有且仅有空桶。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

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

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        if (nums.size() < 2) return 0;
        pair<vector<int>::iterator, vector<int>::iterator> minMax = minmax_element(nums.begin(), nums.end());
        int mini = *minMax.first, maxi = *minMax.second;
        if (mini == maxi) return 0;
        int bucketsNum = nums.size() + 1;
        double bucketsSize = double(maxi - mini) / (bucketsNum - 1);
        vector<pair<int, int>> buckets(bucketsNum, {-1, -1});
        for (int x : nums) {
            int idx = (x - mini) / bucketsSize;
            if (buckets[idx].first == -1) {
                buckets[idx] = { x, x };
            }
            else {
                buckets[idx].first = min(buckets[idx].first, x);
                buckets[idx].second = max(buckets[idx].second, x);
            }
        }
        int pre = -1, res = 0;
        for (auto x : buckets) {
            if (x.first == -1) continue;
            if (pre != -1) res = max(res, x.first - pre);
            pre = x.second;
        }
        return res;
    }
};

刷题总结

这个题目的思想非常好，按照桶排序来求解，思路非常相似，但是桶排序需要对每个桶进行单独排序，在这个算法中我们不需要知道桶内元素的具体顺序，而是只考虑桶和桶之间的差异即可。