排序

164. Maximum Gap

桶排序为数不多（好像仅有？）的排序题。O(n)的时间复杂度。

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 i : nums) {
            min = Math.min(min, i);
            max = Math.max(max, i);
        }

        int gap = (int) Math.ceil((double)(max - min) / (nums.length - 1));

        int[] bucketMIN = new int[nums.length - 1];
        int[] bucketMAX = new int[nums.length - 1];

        Arrays.fill(bucketMIN, Integer.MAX_VALUE);
        Arrays.fill(bucketMAX, Integer.MIN_VALUE);

        for (int i : nums) {
            if (i == min || i == max) continue;
            int index = (i - min) / gap;
            bucketMIN[index] = Math.min(i, bucketMIN[index]);
            bucketMAX[index] = Math.max(i, bucketMAX[index]);
        }
        int maxGap = Integer.MIN_VALUE;
        int prev = min;
        for (int i = 0; i < nums.length - 1; ++i) {
            if (bucketMIN[i] == Integer.MAX_VALUE && bucketMAX[i] == Integer.MIN_VALUE) continue;

            maxGap = Math.max(maxGap, bucketMIN[i] - prev);
            prev = bucketMAX[i];
        }
        maxGap = Math.max(maxGap, max - prev);
        return maxGap;
    }
}