Maximum Gap

https://leetcode.com/problems/maximum-gap/
给定一个无序int数组，求出排序后相邻两个整数最大的差值

Example 1:
Input: [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either
(3,6) or (6,9) has the maximum difference 3.
Example 2:
Input: [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.

• 解题思路
  桶排序 Bucket Sort 来做，首先找出数组的最大值和最小值，然后要确定每个桶的容量，即为 (最大值 - 最小值) / 个数 + 1，在确定桶的个数，即为 (最大值 - 最小值) / 桶的容量 + 1，然后需要在每个桶中找出局部最大值和最小值，而最大间距的两个数不会在同一个桶中，而是一个桶的最小值和另一个桶的最大值之间的间距

上代码

 public int maximumGap(int[] nums) {
        if (nums.length <= 1) {
            return 0;
        }

        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE, n = nums.length, pre = 0, res = 0;
        for (int num : nums) {
            max = Integer.max(max, num);
            min = Integer.min(min, num);
        }

        //bucket的大小
        int size = (max - min) / n + 1;

        //一共有多少个bucket
        int cnt = (max - min) / size + 1;

        int[] bucketMin = new int[cnt];
        int[] bucketMax = new int[cnt];

        Arrays.fill(bucketMin, Integer.MAX_VALUE);
        Arrays.fill(bucketMax, Integer.MIN_VALUE);

        //计算每个bucket内部的最大值和最小值
        for (int num : nums) {
            int idx = (num - min) / size;
            bucketMin[idx] = Math.min(bucketMin[idx], num);
            bucketMax[idx] = Math.max(bucketMax[idx], num);
        }

        for (int i = 1; i < cnt; i++) {
            if (bucketMin[i] == Integer.MAX_VALUE || bucketMax[i] == Integer.MIN_VALUE){
                continue;
            }

            res = Math.max(res,bucketMin[i] - bucketMax[pre]);
            pre = i;
        }

        return res;
    }