LeetCode——最大间距

NO.164 最大间距困难

思路一：比较排序

因为题目中说了”排序后”的相邻元素之间最大的差值。所以最思路就是，先排序，再线性遍历计算出相邻元素之间最大的差值。

public int maximumGap(int[] nums) {
    if (nums.length < 2) return 0;
    Arrays.sort(nums);
    int ans = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        ans = Math.max(ans, nums[i + 1] - nums[i]);
    }
    return ans;
}

但是比较排序的空间上虽然满足，但时间复杂度难易突破 O(nlogn)。

思路二：非比较排序

想要时间复杂度稳定在线性，比较排序暂时是无能为力，所以就想到非比较排序的方法，例如计数排序？先将所有元素统计，不需要完成排序，直接在计数器计算相邻元素之间的差值。

public int maximumGap(int[] nums) {
    //计数
    if (nums.length < 2) return 0;
    int max = nums[0], min = nums[0], bias = 0;
    for (int num : nums) {
        max = Math.max(max, num);
        min = Math.min(min, num);
    }
    bias = 0 - min;
    int[] counter = new int[max - min + 1];
    for (int num : nums) {
        counter[num + bias]++;
    }
    //求最大差值，pre记录前一个元素
    int ans = 0;
    int pre = -1;
    for (int i = 0; i < counter.length; i++) {
        if (counter[i] != 0) {
            if (pre != -1) {
                ans = Math.max(ans, i - pre);
                pre = i;
            } else {
                pre = i;
            }
        }
    }
    return ans;
}

时间复杂度：O(n + K) 两次遍历 + 遍历计数器 O(K) K = max - min

空间复杂度：O(K) 输入 [2,99999999] 内存超出了！！

思路三：桶排序

桶排序也是计数排序的一种，普通的计数排序相当于极端情况下每个桶的区间大小是 1 ，而这里说的桶排序肯定不是这种极端情况，每个桶的区间大小相等，但依然是遍历元素对号入座(放入对应的区间里)。

桶排序的重点就在于，如何规划桶区间的大小和个数，使尽可能少的桶，去覆盖所有的元素。

规划桶大小和数量，必然要知道输入的区间，所以需要知道输入最大元素 max 、最小元素 min，从而知道输入区间总长度 max - min ，用 输入区间总长度/区间个数 得到桶的大小 bucketSize。（区间个数 = 元素个数 - 1）

有了桶的大小，就不难得到桶的数量 (max-min)/bucketSzie + 1 ，为什么要 +1 多一个桶呢？

因为桶内的区间都是前闭后开的，形如 [min,a)、[b,c)、[d,e)、[f,max)，所以如果不 +1 生成的桶将不包含边界值 max 。因此 +1 是为了方便编码，不需要单独去处理边界值 max 。

最后就是找最大间距了！这里需要用到抽屉定理的思想(在 NO.41 缺失的第一个正数题目中也用到过这个思想)，最大间距一定 >= 输入区间大小/输入区间的数量！

//桶结构,桶内只关心最大值、最小值
class Bucket {
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
}

最大间隔一定不会出现在同一个桶内，因此只需要比较桶之间的差值，每个桶内记录最大值、最小值即可！

关于这点 powcai 大佬已经证明的很清楚了！

public int maximumGap(int[] nums) {
    if (nums.length < 2) return 0;
    //找到最小值、最大值
    int max = 0, min = 0;
    for (int num : nums) {
        max = Math.max(max, num);
        min = Math.min(min, num);
    }
    //计算桶大小,桶数量至少一个
    int bucketSize = Math.max((max - min) / (nums.length - 1), 1);
    Bucket[] buckets = new Bucket[(max - min) / bucketSize + 1];
    //入桶,每个桶只关心桶内的最大值和最小值
    for (int i = 0; i < nums.length; i++) {
        int idx = (nums[i] - min) / bucketSize;
        if (buckets[idx] == null) buckets[idx] = new Bucket();
        buckets[idx].max = Math.max(nums[i], buckets[idx].max);
        buckets[idx].min = Math.min(nums[i], buckets[idx].min);
    }
    //前一个桶的 max
    int preMax = -1;
    //最大间隔
    int maxGap = 0;
    for (int i = 0; i < buckets.length; i++) {
        //桶不为空,并且不是第一个桶
        if (buckets[i] != null && preMax != -1) {
            //桶之间的间隔
            maxGap = Math.max(maxGap, buckets[i].min - preMax);
        }
        //记录前一个桶的 max
        if (buckets[i] != null) {
            preMax = buckets[i].max;
        }
    }
    return maxGap;
}

时间复杂度：O(n+m) n 数组长度、m是桶数量

空间复杂度：O(m)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.164 最大间距 困难

思路一：比较排序

思路二：非比较排序

思路三：桶排序

NO.164 最大间距困难