164. 最大间距

class Solution {
    public int maximumGap(int[] nums) {
        int n = nums.length;
        if(n<2)return 0;
        int ans = Integer.MIN_VALUE;
        Arrays.sort(nums);
        for(int i = 1 ;i < n;i++ ) {
            if(Math.abs(nums[i]-nums[i-1])>ans)
                ans = Math.abs(nums[i]-nums[i-1]);
        }
        return ans;
    }
}

更快有桶排序 用了max个桶

• 初级桶排序 因为内存占得太大 导致失败

  class Solution{
    public int maximumGap(int[] nums) {
     int n = nums.length;
     if(n<2) return 0;
     int ans = 0;
     int max = Integer.MIN_VALUE;
     //用了max个桶
     for(int i = 0; i < n ; i++) {
         max = Math.max(max, nums[i]);
     }
     boolean f[]  = new boolean[max+1];
     for(int i = 0; i < n ; i++) {
         f[nums[i]] = true;
  
     }
    int temp = 0;
    boolean begin = false;  //判断哪里是开始
     for(int i = 0 ; i < f.length;i++) {
        if(f[i]==true){
           begin = true; 
           ans = Math.max(ans,temp);//全部都是同一个数导致出现差错 被先加了一个数
           temp = 0;  
        }
        if(begin)
            temp++;
     }
     return ans;
  }
  }

• 桶的数量减少 参考别人的桶排序

  class Solution{
     public int maximumGap(int[] nums) {
        if (nums == null || nums.length < 2)
            return 0;
        int len = nums.length;
        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;
        boolean[] bucket = new boolean[len + 1];
        int[] maxOfBucket = new int[len + 1];
        int[] minOfBucket = new int[len + 1];
        for (int num : nums) {
            int index = getBucketIndex(num, min, max, len);
            maxOfBucket[index] = bucket[index] ? Math.max(maxOfBucket[index], num) : num;
            minOfBucket[index] = bucket[index] ? Math.min(minOfBucket[index], num) : num;
            bucket[index] = true;
        }
        int ret = 0;
        int lastMax = maxOfBucket[0];
        for (int i = 1; i <= len; i++) {
            if (bucket[i]) {
                ret = Math.max(ret, minOfBucket[i] - lastMax);
                lastMax = maxOfBucket[i];
            }
        }
        return ret;
    }
  
    public int getBucketIndex(long num, long min, long max, long len) {
        return (int) ((num - min) * len / (max - min));
    }
  }