图片说明

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));
      }
    }