给定一个数组，求如果排序之后，相邻两数的的最大差值（Java实现）

题目

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

假设输入：
1,7,199,8,12,45,99,2,3,4

输出：
100

分析

首先根据题意，时间复杂度能到O(n)的排序都是非基于比较的排序，我们肯定不能用排序了，但是我们可以借鉴桶排序的思想

假设我们有n个元素
1、我们创建n + 1个桶，由于第一个元素和最后一个元素肯定在第一个桶和最后一个桶内，所以中间肯定有空桶
2、然后我们找出数组中的最大值和最小值，根据最大值和最小值可以计算出每个桶的容量
3、由于我们希望求最大差值，根据第一步我们知道必定有空桶，那么空桶后面的桶内的最小值减去空桶前面的桶内的最大值必定会大于桶内的值相减，说起来比较难理解，下面举个例子
假设桶内元素如图

已知4号桶为空桶，设上图中5号桶内的min减去3号桶内的max的差为x，5号桶内的max减去5号桶内的min的差为y，那么x必定会大于y，其实x会大于所有的桶内元素相减的差
4、既然中间必定有一个空桶，并且跨桶相减会大于桶内相减，那么我们就可以不用考虑桶内的值相减了，我们对于每个桶只记录最大值和最小值就可以，然后也不用再去计算桶内的值相减了，只要跨桶相减就行了

实现

有了上面的思路，就可以开始写代码了

    public static int getMaximumValues(int arr[]) {
        // 先遍历数组找出最小值和最大值
        // 为了能正确找到最大值和最小值，将初始最大值设置为int的最小值，最小值设为int最大值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(arr[i], max);
            min = Math.min(arr[i], min);
        }

        // 创建三个数组，分别记录每个桶的最大值、最小值、以及是否有值
        // 假设有n个元素，那么就创建n+1个桶
        // 因为第一个元素肯定在第一个桶，最后一个元素肯定在最后一个桶，那么中间必定会有空桶
        // 隔着桶相减的值必定会大于一个桶内最大值和最小值的相减
        // 中间最少有一个桶为空桶保证了至少会有一个隔着桶相减的差值
        // 那么我们就不用考虑桶内相减的值了，只需要考虑两个桶之间的差值中的最大值就可以了
        // 然后记录下最大的差值就可以了
        int n = arr.length + 1;
        boolean[] hashNum = new boolean[n];
        int[] maxs = new int[n];
        int[] mins = new int[n];

        for (int i = 0; i < arr.length; i++) {
            int bucket = getBucket(arr[i], arr.length, max, min);//计算应该在那个桶内
            maxs[bucket] = hashNum[bucket] ? Math.max(arr[i], maxs[bucket]) : arr[i];
            mins[bucket] = hashNum[bucket] ? Math.min(arr[i], mins[bucket]) : arr[i];
            hashNum[bucket] = true;
        }

        //记录结果，每次找到更大的差值会更更新此值
        int res = 0;
        // 记录上一次出现的最大值，每次循环从下一个有值的桶内找到最小值减去上一次记录的最大值，就是要求的差值
        // 第一个桶必定有值，并且第一个桶内的最大值减去最小值必定不是最大差值，所以只取第一个桶的最大值就可以了
        int lastMax = maxs[0];
        for (int i = 1; i < n; i++){
            if(hashNum[i]){// 如果桶内有值才减去上一次记录的最大值
                // 取新计算的差值和旧的差值中较大的那个
                res = Math.max(mins[i] - lastMax, res);
                lastMax = maxs[i];//更新上一个最大值
            }
        }
        return res;
    }

    /**
     * 计算应该在那个桶内
     * @param num
     * @param n
     * @param max
     * @param min
     * @return
     */
    private static int getBucket(int num, int n, int max, int min) {
        return ((num - min) * n / (max - min));
    }