力扣164:最大间距

题目

给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0 。

您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。

思路

这道题的思路很简单我们使用合适的排序方法后就可以很顺利的找到最大差值了，那么关键是合法的排序方法是什么？我们常见的排序有：快排，归并，希尔，堆排等等。题目要求我们的时间复杂度和空间复杂度都是O(N)，那么有哪些排序是可以完成这个要求的呢？下图是常见的排序的时间复杂度和空间复杂度。

我们发现只有桶排序和基数排序是符合这个要求的但是桶排序在最坏的情况下还有可能达到O(N^2)。所以我们使用基数排序来完成。

代码

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) {
            return 0;
        }
        else if(n == 2)
        {
            return abs(nums[1] - nums[0]);
        }
        // 寻找最大值也就是知道有几位数
        int maxval = *max_element(nums.begin(),nums.end());

        vector<int> res(n);
        long exp = 1;
        while (maxval >= exp) {
            // 十个桶
            vector<int> cnt(10);
            // 判断每个桶里有几个数
            for (int i = 0; i < n; i++) {
                int dig = (nums[i] / exp) % 10;
                cnt[dig]++;
            }
            // 将桶中存储的几个数转换为每个桶里数的下标
            // 也就是桶中的数前面有几个数
            for (int i = 1; i < 10; i++) {
                cnt[i] += cnt[i - 1];
            }
            // 将原数组的数按照顺序来放到新数组中
            for (int i = n - 1; i >= 0; i--) {
                int dig = (nums[i] / exp) % 10;
                res[cnt[dig] - 1] = nums[i];
                cnt[dig]--;
            }
            copy(res.begin(),res.end(),nums.begin());
            exp *= 10;
        }
        int maxdiff = 0;
        for(int i = 1; i < n;i++)
        {
            maxdiff = max(maxdiff,nums[i] - nums[i-1]);
        }
        return maxdiff;
    }
};