164. Maximum Gap

//O(n) time and space
class Solution {
    public int maximumGap(int[] nums) {
        if(nums==null || nums.length<2) return 0;
        int n = nums.length, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for(int num:nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        int gap = (int)Math.ceil((double)(max - min)/(n - 1));
        int[] bucketsMin = new int[n-1];
        int[] bucketsMax = new int[n-1];
        Arrays.fill(bucketsMin, Integer.MAX_VALUE);
        Arrays.fill(bucketsMax, Integer.MIN_VALUE);
        for(int num:nums) {
            if(num == min || num==max) continue;
            int index = (num-min)/gap;
            bucketsMin[index] = Math.min(bucketsMin[index], num);
            bucketsMax[index] = Math.max(bucketsMax[index], num);
        }
        int result = Integer.MIN_VALUE, prev = min;
        for(int i=0;i<n-1;i++) {
            if((bucketsMax[i]==Integer.MIN_VALUE)&&(bucketsMin[i]==Integer.MAX_VALUE)) continue;
            result = Math.max(result, bucketsMin[i]-prev);
            prev = bucketsMax[i];
        }
        result = Math.max(result, max-prev);
        return result;
    }
}