164. 最大间距

public int maximumGap(int[] nums) { int n = nums.length; if (n <= 1) return 0; int minVal = nums[0]; int maxVal = nums[0]; for (int i = 1; i < n; i++) { if (nums[i] > maxVal) maxVal = nums[i]; if (nums[i] < minVal) minVal = nums[i]; } // 桶内间隔 int gap = (int) Math.ceil((maxVal - minVal) * 1.0 / (n-1)); //桶的个数 n-1 int[] bucketMin = new int[n-1]; int[] bucketMax = new int[n-1]; Arrays.fill(bucketMax, Integer.MIN_VALUE); Arrays.fill(bucketMin, Integer.MAX_VALUE); for (int i = 0; i < n; i++) { if (nums[i] == minVal || nums[i] == maxVal) continue; // nums[i] 应该存放的下标位置 int idx = (nums[i] - minVal) / gap; if (nums[i] > bucketMax[idx]) bucketMax[idx] = nums[i]; if (nums[i] < bucketMin[idx]) bucketMin[idx] = nums[i]; } int prev = minVal; int maxGap = 0; // 遍历桶 for (int i = 0; i < n-1; i++) { if (bucketMax[i] == Integer.MIN_VALUE && bucketMin[i] == Integer.MAX_VALUE) continue; maxGap = Math.max(maxGap, bucketMin[i] - prev); prev = bucketMax[i]; } maxGap = Math.max(maxGap, maxVal - prev); return maxGap; }