LeetCode164. 最大间距

题目链接：Leetcode164展开目录

题解展开目录

这道题用到了桶排序的思想，但是跟排序没啥关系，思路是这样的，数组中有 n 个元素，那么就构建 n+1 个桶，桶的属性有三个，最大值最小值以及是否为空。桶的下标从 0 到 n，然后遍历一遍数组，将其中最小值放到 0 号桶的位置，最大值放到 n 号桶的位置，这样的话 1~n-1 号桶应该放什么数就很清楚了，然后再遍历一遍数组，将其中的所有元素放至应该放到的桶内，并且维护桶的属性，即每个桶的最大值和最小值以及是否为空

最后遍历一遍桶，用当前桶的最小值减去上一个桶的最大值，找到最大的那个数即是答案

简单解释一下为什么这样做一定是对的。首先我们有 N 个数，N+1 个桶，同时由于 0 号桶以及 N 号桶都放了数，根据鸽笼原理，中间一定至少有一个桶最终是空的，而最大间距也一定来空桶的左右两边，即空桶左边桶的最小值减去空桶右边桶的最大值

代码展开目录

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