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

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

示例 1:

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

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

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

解题思路：这道题要用线性时间复杂度完成排序，因此只能考虑基数排序和桶排序，关于这两种排序算法，还需要好好去了解一下，下面用了桶排序的思路解决这个问题，还需要证明一下，首先，假设输入数组的最大值为maxVal，最小值为minVal，有一个结论是相邻数字的最大间隔不小于floor((maxVal-minVal)/(n-1))，其中n是输入数组的元素个数，这里可以用反证法来证明，因为n-1其实是间隔个数，用floor((maxVal-minVal)/(n-1))表示平均间隔向下取整，假设所有间隔都小于floor((maxVal-minVal)/(n-1))，那最后将这些间隔加起来，必定小于(maxVal-minVal)，但数组的这些间隔和肯定是(maxVal-minVal)的，所以这里出现了矛盾，因此结论成立，相邻数字的最大间隔不小于floor((maxVal-minVal)/(n-1))，因此我们可以把一个桶的大小设置为floor((maxVal-minVal)/(n-1))，然后就可以推出间隔最大的相邻数组必定不在同一个桶内，而是在不同桶（有可能相邻也可能不相邻），因此我们用桶来维护桶内数字的最大值和最小值，把所有数字放入桶以后，从头开始遍历，然后动态更新最大间隔的大小。

代码 t22 s20 java

class Solution {
    public int maximumGap(int[] nums) {
        int n = nums.length;
        if(n<2) return 0;
        int maxVal = Arrays.stream(nums).max().getAsInt();
        int minVal = Arrays.stream(nums).min().getAsInt();
        int width = Math.max(1, (maxVal - minVal) / (n-1));
        int bucket = (maxVal - minVal) / width + 1;
        int[][] bucketList = new int[bucket][2];
        for(int i=0; i<bucket; i++){
            Arrays.fill(bucketList[i], -1);
        }

        for(int i=0; i<n; i++){
            int t = (nums[i] - minVal) / width;
            if(bucketList[t][0]==-1){
                bucketList[t][0] = nums[i];
                bucketList[t][1] = nums[i];
            }else{
                bucketList[t][0] = Math.min(bucketList[t][0], nums[i]);
                bucketList[t][1] = Math.max(bucketList[t][1], nums[i]);
            }
        }

        int res = 0, pre = -1;
        for(int i=0; i<bucket; i++){
            if(bucketList[i][0]==-1) continue;
            if(pre!=-1){
                res = Math.max(res, bucketList[i][0] - bucketList[pre][1]);
            }
            pre = i;
        }
        return res;
    }
}

参考资料：
https://leetcode-cn.com/problems/maximum-gap/solution/zui-da-jian-ju-by-leetcode-solution/

164. 最大间距