LeetCode 164. 最大间距：桶排序与鸽巢原理的精妙结合

一、题目

给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0 。

您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。

1.问题本质

如果直接排序再扫描，时间复杂度 O(n*logn)，空间复杂度 O(1) 或 O(n)（取决于排序算法）。

但题目有个进阶要求：尝试在线性时间和空间内解决此问题。

二、解题思路

1.暴力求解

最直观的求解方式就是暴力求解，即直接排序，然后用一层for循环求解每两个相邻的数字之间的间距，最终得出最大值。

但这样，时间复杂度最低也得是O(n*logn)

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

2.突破思路：从排序到分桶

2.1.核心突破口

排序需要比较，而比较排序的下限是 O(n*log n)。要在线性时间内解决，必须避免完全排序，只需要找到最大间距。

思考如下内容：

• 如果数组长度为 n，值范围为 [min, max]
• 最大间距至少为 (max - min) / (n - 1)
  • 为什么？
  • 假设均匀分布，每个”桶”的大小至少是这个值；
  • 如果分布不均匀，那肯定有比这个数大的，也有比这个数小的，因为这个数是平均数。

2.2.鸽巢原理

鸽巢原理（抽屉原理）：如果有 n 个物品放入 m 个容器，且 n > m，那么至少有一个容器包含多于一个物品。

在本题中的逆向应用：

• 如果我们要找最大间距，可以考虑将数字分配到桶中
• 如果桶的数量足够多，最大间距就不可能出现在同一个桶内
• 最大间距一定出现在不同桶之间

2.3.桶排序思想

1. 创建 n-1 个桶（因为有 n 个数，最多 n-1 个间隔）
2. 每个桶的范围 = (max - min) / (n - 1)
3. 将数字放入对应的桶中
4. 最大间距一定出现在不同桶之间，而不是桶内部

2.4桶设计

设：

• minVal = 数组最小值
• maxVal = 数组最大值
• n = 数组长度
• bucketSize = Math.max(1, (maxVal - minVal) / (n - 1))（至少为1）
• bucketCount = (maxVal - minVal) / bucketSize + 1

关键：

• 每个桶只记录进入该桶的最小值和最大值
• 最大间距 = 相邻非空桶之间（后桶最小值 - 前桶最大值）的最大值

思考：为什么最大间距一定在不同的桶之间？

假设排序后的数组为：a₁ ≤ a₂ ≤ … ≤ aₙ 最大间距为：max_gap = max(aᵢ₊₁ - aᵢ)

设：

• 平均间距 gap_avg = (aₙ - a₁) / (n-1)
• 桶大小 b = ⌊(aₙ - a₁) / (n-1)⌋ ≤ gap_avg

对于任意 i，如果 aᵢ₊₁ 和 aᵢ 在同一个桶内：aᵢ₊₁ - aᵢ ≤ b ≤ gap_avg ≤ max_gap

因此，产生最大间距的两个数一定在不同的桶中。

三、算法步骤

1. 找到数组的最小值 minVal 和最大值 maxVal
2. 如果 minVal == maxVal，直接返回 0（所有元素相同）
3. 计算桶大小：bucketSize = Math.max(1, (maxVal - minVal) / (n - 1))
4. 创建桶数组，每个桶记录 min 和 max
5. 遍历数组，将每个数放入对应的桶
6. 遍历所有桶，计算相邻非空桶之间的间距

四、代码实现

class Solution {
    /**
    对于这个题，如果不考虑时间复杂度，根本没什么难度，但是对于线性时间的这个要求，就需要好好考虑一下
    鸽巢原理：如果数组长度为n，值范围为[min,max],那么最大间距至少为（max-min）/（n-1）
    桶排序思想：创建n-1个桶，每个桶的范围=（max-min）/（n-1），将数组中的所有数字放在桶中，那么最大间距一定出现在桶之间，而不是桶内部。因为桶内部的距离 <=（max-min）/（n-1）
     */
    public int maximumGap(int[] nums) {
        int n = nums.length;
        if(n<=1) return 0;

        //1.找到最大值和最小值
        int minVal=nums[0],maxVal=nums[0];
        for(int num : nums){
            minVal = Math.min(minVal,num);
            maxVal = Math.max(maxVal,num);
        }
        //所有数字相同
        if(minVal==maxVal) return 0;
        //2.计算桶大小和数量
        int bucketSize = Math.max(1,(maxVal-minVal)/(n-1));
        int bucketCount = (maxVal-minVal)/bucketSize+1;
        //3.初始化桶
        //每个桶只需要记录最大值和最小值，因为这道题只需要得出最大间距即可
        int[] bucketMin = new int[bucketCount];
        int[] bucketMax = new int[bucketCount];
        Arrays.fill(bucketMin,Integer.MAX_VALUE);
        Arrays.fill(bucketMax,Integer.MIN_VALUE);
        //4.将数字放入桶中
        for(int num : nums){
            int bucketIndex = (num-minVal)/bucketSize;
            bucketMin[bucketIndex] = Math.min(bucketMin[bucketIndex], num);
            bucketMax[bucketIndex] = Math.max(bucketMax[bucketIndex], num);
        }
        //5.计算最大间距
        int maxGap = 0;
        int preMax = bucketMax[0];
        for(int i=1;i<bucketCount;i++){
            if(bucketMin[i] == Integer.MAX_VALUE) continue;
            maxGap = Math.max(maxGap, bucketMin[i]-preMax);
            preMax = bucketMax[i];
        }
        return maxGap;
    }
}