1. 题目

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

如果数组元素个数小于 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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题思路

很显然，排好序遍历一遍即可。线性时间复杂度的排序法为基数排序。虽然其时间复杂度为线性，但是其常数太大了，跑起来竟然和快速排序差不多。

3. 代码

class Solution {
public:
    void countSort(vector<int>& nums, int exp){
        vector<int> count(10,0),res(nums.size());

        for(auto &x: nums) count[(x/exp)%10]++;
        partial_sum(count.begin(),count.end(),count.begin());
        for(int i=nums.size()-1;i>=0;--i) res[--count[(nums[i]/exp)%10]]=nums[i];
        nums.assign(res.begin(),res.end());
    }
    void radixSort(vector<int>& nums){
        int range = *max_element(nums.begin(),nums.end());

        for(int exp=1;range/exp>0;exp*=10){
            countSort(nums,exp);
        }

    }
    int maximumGap(vector<int>& nums) {
        int len = nums.size();
        if(len < 2) return 0;
        radixSort(nums);
        int res = 0;
        for(int i=1;i<len;++i){
            res = max(res,nums[i]-nums[i-1]);
        }
        return res;
    }
};