Leetcode 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.

思路：
找到最小的bucketSize，生成buckets，把每个num放到对应bucket中，同时更新这个bucket的最大值和最小值。
遍历buckets，比较相邻bucket的min和max的最大差值，更新maximum。

class Bucket {
    public boolean used = false;
    public int min = Integer.MAX_VALUE;
    public int max = Integer.MIN_VALUE;
}

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

    //n elem, n-1 buckets
    int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    for (int i = 0; i < nums.length; i++) {
        max = Math.max(max, nums[i]);
        min = Math.min(min, nums[i]);
    }

    int bucketSize = (int)Math.ceil((double)(max - min) / (nums.length - 1));;
    if (bucketSize == 0) {
        return 0;
    }

    int bucketNum = (max - min) / bucketSize + 1;
    Bucket[] buckets = new Bucket[bucketNum];
    for (int i = 0; i < buckets.length; i++) {
        buckets[i] = new Bucket();
    }
    // Arrays.fill(buckets, new Bucket());

    for (int num : nums) {
        int bucketIndex = (num - min) / bucketSize;
        buckets[bucketIndex].used = true;
        buckets[bucketIndex].min = Math.min(buckets[bucketIndex].min, num);
        buckets[bucketIndex].max = Math.max(buckets[bucketIndex].max, num);
    }

    int preMax = min, maxGap = 0;
    for (Bucket bucket : buckets) {
        if (!bucket.used) {
            continue;
        }
        maxGap = Math.max(maxGap, bucket.min - preMax);
        preMax = bucket.max;
    }

    return maxGap;
}