164. Maximum Gap

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.

解题思路为bucket sort。

先找到min和max，则max gap不会小于ceil[(max-min)/(N-1)]。 令gap = ceil[(max-min)/(N-1)]，我们将数字放在N-1个bucket中。 其中k-th个bucket中包含数字范围[min+(k-1)gap, min+kgap)。 由于将N-2个数字放入N-1个bucket中，至少一个bucket是空的，对于每一个bucket，我们只需存其中的最小值和最大值。 max gap一定为bucket的最小值减去前一个bucket(非空)的最大值。 两个端点的情况也要考虑。

public 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);
        }
        int gap = (int) Math.ceil((double)(max - min)/(nums.length-1));
        int[] bucketsMin = new int[nums.length-1];
        int[] bucketsMax = new int[nums.length-1];
        Arrays.fill(bucketsMin, Integer.MAX_VALUE);
        Arrays.fill(bucketsMax, Integer.MIN_VALUE);
        for(int num : nums) {
            if(num == min || num == max) continue;
            int idx = (num - min) / gap;
            bucketsMin[idx] = Math.min(bucketsMin[idx], num);
            bucketsMax[idx] = Math.max(bucketsMax[idx], num);
        }
        int maxGap = 0;
        int prev = min;
        for(int i = 0; i < nums.length-1; i++) {
            if(bucketsMin[i] == Integer.MAX_VALUE && bucketsMax[i] == Integer.MIN_VALUE) continue;
            maxGap = Math.max(maxGap, bucketsMin[i] - prev);
            prev = bucketsMax[i];
        }
        maxGap = Math.max(maxGap, max - prev);
        return maxGap;
    }
}