思路：

1.利用桶排序的思想，先求出原数组从最小值Min到最大值Max的单位区间长度d，d=(Max-Min)/n。算出d的作用是为了后续确定各个桶的区间范围划分。

2.创建一个长度是N+1的数组Array，数组的每一个元素都是一个List，代表一个桶。

3.遍历原数组，把原数组每一个元素插入到新数组Array对应的桶当中，进入各个桶的条件是根据不同的数值区间（数值区间如何划分，看后面的图就明白了）。由于桶的总数量是N+1，所以至少有一个桶是空的。

4.遍历新数组Array，计算每一个空桶右端非空桶中的最小值，与空桶左端非空桶的最大值的差，数值最大的差即为原数组排序后的相邻最大差值。

我的想法：

就是将数组里面的数据当初一条线，切分成n等份，即n个空桶，n值尽可能的小，节省空间，最好为数组长度+1

最小值肯定在第一个里面，最大值在最后一个桶里面，中间的数据可能有多个在同一个桶里面（只要桶内相对的最大值，最小值即可，其他的可以不要），也有桶一直都是空格

后面比较相邻桶中最大值与下一个桶（没有数据的桶可以跳过）中的最小值差额即可！

Code:

package com.qhong.dataStructures;import java.util.Arrays;public class MaxGapDemo {    public static int maxGap(int[] nums) {        if (nums == null || nums.length < 2) {            return 0;        }        int len = nums.length;        int min = Integer.MAX_VALUE;        int max = Integer.MIN_VALUE;        for (int i = 0; i < len; i++) {            min = Math.min(min, nums[i]);            max = Math.max(max, nums[i]);        }        if (min == max) {            return 0;        }        System.out.println(String.format("max:%d ,min:%d",max,min));        boolean[] hasNum = new boolean[len + 1];        int[] maxs = new int[len + 1];        int[] mins = new int[len + 1];        int bid = 0;        for (int i = 0; i < len; i++) {            bid = bucket(nums[i], len, min, max); // 算出桶号            System.out.println(String.format("%d : %d",nums[i],bid));            mins[bid] = hasNum[bid] ? Math.min(mins[bid], nums[i]) : nums[i];            maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], nums[i]) : nums[i];            hasNum[bid] = true;        }        System.out.println(Arrays.toString(mins));        System.out.println(Arrays.toString(maxs));        int res = 0;        int lastMax = 0;        int i = 0;        while (i <= len) {            if (hasNum[i++]) { //找到第一个不为空的桶                lastMax = maxs[i - 1];                break;            }        }        System.out.println(String.format("i:%d",i));        for (; i <= len; i++) {            if (hasNum[i]) {                System.out.println(String.format("lastMax:%d",lastMax));                System.out.println(String.format("res:%d",res));                res = Math.max(res, mins[i] - lastMax);                lastMax = maxs[i];            }        }        return res;    }    //使用long类型是为了防止相乘时溢出    public static int bucket(long num, long len, long min, long max) {        return (int) ((num - min) * len / (max - min));    }    public static void main(String[] args) {        int[] arr={2, 6, 3, 4, 5, 10, 9};        int num=maxGap(arr);        System.out.println(num);//        int[] arr2={0, 6, 3, 16, 7, 10, 9, 11, 20, 18 };//        System.out.println(maxGap(arr2));    }}

Output:

max:10 ,min:22 : 06 : 33 : 04 : 15 : 210 : 79 : 6[2, 4, 5, 6, 0, 0, 9, 10][3, 4, 5, 6, 0, 0, 9, 10]i:1lastMax:3res:0lastMax:4res:1lastMax:5res:1lastMax:6res:1lastMax:9res:33