public class _164 {
    static class Solution {
        public int maximumGap(int[] nums) {
            //discuss中的桶排序
            if (nums.length <= 1) return 0;
            if (nums.length == 2) {
                return Math.abs(nums[0] - nums[1]);
            }
            //n个元素 分布在 [min,max]区间中，它的最大gap>=( max-min) /(n-1)
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            for (int val : nums) {
                max = Math.max(val, max);
                min = Math.min(val, min);
            }
            int n = nums.length;
            int gap = (int) Math.ceil((double) (max - min) / (n - 1));//向上取整
            if (gap == 0) return 0;
            int size = max / gap + 1;
            Integer[] maxNums = new Integer[size];
            Integer[] minNums = new Integer[size];
            for (int val : nums) {
                int idx = val / gap;
                maxNums[idx] = maxNums[idx] == null ? val : Math.max(val, maxNums[idx]);
                minNums[idx] = minNums[idx] == null ? val : Math.min(val, minNums[idx]);
            }
            int pre = Integer.MAX_VALUE;
            //拿每组最小的减去前个有效组的最大值
            for (int i = 0; i < minNums.length; i++) {
                if (minNums[i] != null) {
                    gap = Math.max(gap, minNums[i] - pre);
                    pre = maxNums[i];
                }
            }
            return gap;
        }
    }
}