题目：

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

解答：

这题挺难理解的，但是可以举例，比如说现在有1, 3, 5, 9。那么我们可以把它分成3个bucket来装，min表示在这个bucket范围中，存在的最小数和最大数。这个bucket的长度是最小可能的最大差值。（如果哪个差值比这个还小，那么为了填补这个小差值，就必然存在另一个差值比它大，那么这个数组的最大差值就比当前bucket大。所以均分下来的bucket是最小可能的最大差值）

b0: (1, 3) min = Integer.max, max = Integer.min

b1: (4, 6) min = Integer.max, max = Integer.minb2: (7, 9) min = Integer.max, max = Integer.min

然后我们来看这个数组里的数在哪个bucket里，用(nums(i) - min) / gap来得到，

第一个数1在b0中，所以我们更新:b0: (1, 3) min = 1, max = 1;第二个数3在b0中，所以我们更新：b0: (1, 3) min = 1, max = 3;第三个数5在b1中，所以我们更新：b1: (4, 6) min = 5, max = 5;..依次这样下去。因为每个bucket中的最大值－最小值就是我们最小的gap, 所以我们不用计算相邻的两个数，我们只要比较后一个bucket中的最小值和前一个bucket中的最大值相差多少，取最大相差的值就是最终的结果。注意考虑min和max两个边界值也要加进去。

public int maximumGap(int[] nums) {        if (nums == null || nums.length < 2) return 0;                int len = nums.length;        int max = nums[0], min = nums[0];        for (int i = 0; i < nums.length; i++) {            max = Math.max(max, nums[i]);            min = Math.min(min, nums[i]);        }        //Math.ceil与最小的比这个数大的蒸熟，使bucket可以包含所有数        int gap = (int)Math.ceil((double)(max - min) / (len - 1));                int[] BucketsMIN = new int[len - 1];        int[] BucketsMAX = new int[len - 1];        Arrays.fill(BucketsMIN, Integer.MAX_VALUE);        Arrays.fill(BucketsMAX, Integer.MIN_VALUE);        for (int num : nums) {            //不考虑边界，所以把边界的min和max都拿出来，单独再考虑            if (num == min || num == max) continue;                        int bucket = (num - min) / gap;            BucketsMIN[bucket] = Math.min(BucketsMIN[bucket], num);            BucketsMAX[bucket] = Math.max(BucketsMAX[bucket], num);        }                int result = 0;        int previous = min;        for (int i = 0; i < len - 1; i++) {            if (BucketsMIN[i] == Integer.MAX_VALUE && BucketsMAX[i] == Integer.MIN_VALUE) {                continue;            }            result = Math.max(result, BucketsMIN[i] - previous);            previous = BucketsMAX[i];        }        result = Math.max(result, max - previous);        return result;    }