164. Maximum Gap

Version #2 Bucket Sort
Time O(n)
Space O(n)
以前理解的bucket sort每个bucket只放一个num
但是也可以把num按range压缩，每个bucket放一个范围内的num

65.47 %
class Solution {
    public int maximumGap(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        int min = nums[0];
        int max = nums[0];
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        if (max == min) {
            return 0;
        }
        // N nums -> (N - 1) gaps -> ths max gap should be at least = (max - min) / (N - 1)
        // For all gaps less than this, we don't care
        // 1 3 6 9 -> 8/3 = 3 min diff -> bucket -> Math.ceil((max-min) / ((max - min) / (n - 1)))
        int N = nums.length;
        int gap = (int)Math.ceil(1.0 * (max - min) / (N - 1));
        Integer[] bucketMin = new Integer[N];
        Integer[] bucketMax = new Integer[N];
        for (int num : nums) {
            int index = (num - min) / gap;
            bucketMin[index] = bucketMin[index] == null ? num : Math.min(bucketMin[index], num);
            bucketMax[index] = bucketMax[index] == null ? num : Math.max(bucketMax[index], num);
        }
        int result = 0;
        int prev = -1;
        for (int i = 0; i < N; i++) {
            if (bucketMin[i] == null) {
                continue;
            }
            result = Math.max(result, bucketMax[i] - bucketMin[i]);
            if (prev != -1) {
                result = Math.max(result, bucketMin[i] - bucketMax[prev]);
            }
            prev = i;
        }
        return result;
    }
   
}

Version #1
Sort and Iterate
Time O (nlogn)
Space O (1)
65.47 %
class Solution {
    public int maximumGap(int[] nums) {
        Arrays.sort(nums);
        int diff = 0;
        for (int i = 1; i < nums.length; i++) {
            diff = Math.max(diff, nums[i] - nums[i - 1]);
        }
        return diff;
    }
}