LeetCode164. 最大间距

class Solution {
    class Bucket {
        int max,min;
        boolean hasNum;
    }
    public int maximumGap(int[] nums) {
        int len = nums.length;
        Bucket[] bucket = new Bucket[len + 1];
        for(int i = 0;i <= len;i++)
            bucket[i] = new Bucket();
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i:nums) {
            max = Math.max(max,i);
            min = Math.min(min,i);
        }
        if(max == min) 
            return 0;
        for(int i = 0;i < len;i++) {
            int idx = put(nums[i],max,min,len);
            if(!bucket[idx].hasNum) {
                bucket[idx].max = nums[i];
                bucket[idx].min = nums[i];
                bucket[idx].hasNum = true;
            } else {
                bucket[idx].max = Math.max(bucket[idx].max,nums[i]);
                bucket[idx].min = Math.min(bucket[idx].min,nums[i]);
            }
        }
        int res = 0;
        int lastMax = bucket[0].max;
        int i = 1;
        for(;i <= len;i++) {
            if(bucket[i].hasNum) {
                res = Math.max(res,bucket[i].min - lastMax);
                lastMax = bucket[i].max;
            }
        }
        return res;
    }
    public static int put(long num,long max,long min,long len) {//计算放在几号桶
        return (int)((num - min) * len / (max - min));
    }
}