给定一个未排序的数组，求如果数组排序之后，相邻数的最大差值。要求时间复杂度为O(n),且要求不能用非基于比较的排序。

首先，这个问题明显限制了不能使用直接排序的方式求解。因为基于比较的排序时间复杂度最低也是O(nlogn)，而且题目限制不能使用非基于比较的排序。所以我们需要另想思路。

我们可以看到上面的解题思路，首先我们遍历一次数组，得到数组中的max和min。把(max-min)切分为N+1个桶，最大差值必然是两个相邻桶的（右桶的min-左桶的max）。

为什么呢？为什么同一个桶里面不会存在最大差值呢？

根据抽屉原理：把N个苹果放到N+1个抽屉里面，必然至少有一个抽屉不存在苹果。

而我们这里，一个桶代表一个差值，而我们这样设计的结果就是，必然存在一个空桶。所以这个最大差值必然大于一个桶代表的范围。

有的同学可能要问了：为什么我们不直接找空桶，空桶附近的不就是最大差值吗？

我们考虑这样一种情况：假设我们有两个相邻的桶（中间没有空桶）{5 , 8} {8,11},假设我们得到的结果中，{5,8}这个桶得到的max是5，{8,11}得到的min是11，那么我们的差值就是6了，而一个空桶的差值只有3。

代码如下：

import org.junit.Test;

/**
 * 给定一个未排序的数组，求如果数组排序之后，相邻数的最大差值
 */
public class MaxGap {
    static class Tong{
        boolean isEmpty=true;
        int max;
        int min;
    }

    @Test
    public void test(){
        int[] arr = {3, 2, 7, 5, 6, 1, 10};
        int maxGap = getMaxGap(arr);
        System.out.println(maxGap);
    }


    public int getMaxGap(int[] arr) {
        // 遍历一次数组，获得最大值和最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i = 0;i < arr.length;i++){
            max = arr[i]>max?arr[i]:max;
            min = arr[i]<min?arr[i]:min;
        }
        if(max == min) {
            return 0;
        }
        // 将max - min 分成 N+1 个桶
        // 第i个桶的范围为min+i*tongGap - min + (i+1)*tongGap    i为0-N
        // 遍历数组，把数组中的数加入到桶
        Tong[] tongs = new Tong[arr.length+1];
        for(int i=0;i<tongs.length;i++){
            tongs[i] = new Tong();
        }
        for(int i=0;i < arr.length;i++){
            int j = bucket(arr[i],arr.length,max,min);
            if(tongs[j].isEmpty){
                tongs[j].max = arr[i];
                tongs[j].min = arr[i];
                tongs[j].isEmpty = false;
            }else{
                if(arr[i] > tongs[j].max){
                    tongs[j].max = arr[i];
                }
                if(arr[i] < tongs[j].min){
                    tongs[j].max = arr[i];
                }
            }
        }
        int curMax = Integer.MIN_VALUE;
        boolean isInit = false;
        int maxGap = Integer.MIN_VALUE;
        // 遍历非空桶，相邻右桶的最小值-相邻左桶的最大值，比较最大值
        for(int i=0;i<tongs.length;i++){
            if(tongs[i].isEmpty){
                continue;
            }
            if(!isInit){
                // 第一个桶
                curMax = tongs[i].max;
                isInit = true;
                continue;
            }else{
                // 不是第一个桶
                int gap = tongs[i].min - curMax;
                maxGap = maxGap<gap?gap:maxGap;
                curMax = tongs[i].max;
            }

        }
        return  maxGap;
    }
    // 获得num放在哪个桶的index
    public int bucket(long num,long len,long max,long min){
        // 必须要先乘后除，不然会等于0
        return (int)((num-min)*len/(max-min));
    }
}