技术总监拿了45万年终奖突然离职，我们以为是被别人挖走了，结果内幕是总监发现自己管理的两个核心项目，被公司偷偷转移给新空降的领导

面试题：最大间距

昨天晚上下班地铁上人巨多，我一手拉着扶手，一手刷题，刚好刷到这个“最大间距”，脑子一热想了半天，回家路上都忘了吃宵夜…就跟你聊聊这题咋想、咋写 Java 代码吧。

题目意思很简单：给你一个无序的整型数组，先把它排好序，然后看相邻两个数之间的差，这些差里面最大的那个，就是“最大间距”。

比如：[3, 6, 9, 1]排完序是 [1, 3, 6, 9]间距分别是：2、3、3，所以答案是 3。

如果数组长度小于 2，那肯定没有间距，直接返回 0 就行了。

很多面试题就这么点事儿，但人家会加一句：**要求时间复杂度 O(n)**，这里才是重点。

别想太多，直接排序。

1. 用库函数 Arrays.sort(nums)，复杂度 O(n log n)；
2. 再从头扫到尾，维护一个 maxGap，每次拿相邻两个数的差更新一下。

Java 代码大概这样：

publicintmaximumGapSort(int[] nums){
if (nums == null || nums.length < 2) {
return0;
    }
    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;
}

如果只是日常业务里用用，这个版本 99% 场景都够了，简单粗暴。但是面试官肯定要继续追

这个 O(n) 其实不难，就是有点“反直觉”。

先想几个事实：

• 数组里一共有 n 个数；
• 排序后会有 n-1 个间距；
• 假设最小值是 min，最大值是 max，那所有间距的总和就是 max - min。

那平均每个间距大概是：

平均间距 = (max - min) / (n - 1)

鸽巢原理那一套就来了： 如果你把这 n 个数，塞进 n-1 个“桶”里，真正的最大间距，一定会出现在两个桶之间，而不是一个桶里面。

为啥？因为：

• 同一个桶里，数的范围不会超过我们设计的“桶大小”，“桶内最大差”肯定 ≤ 桶大小。
• 真正的大间距，肯定是“前一个非空桶的最大值”和“下一个非空桶的最小值”之间拉开的。

所以我们根本不用把每个桶里所有元素都存下来，只存两样东西就够了：

• 这个桶里的 最小值
• 这个桶里的 最大值

按做题视角说一下整套流程：

1. 遍历一遍数组，找出全局 min 和 max；

2. 如果 min == max，那所有数都一样，最大间距 = 0；

3. 计算桶大小：

   int bucketSize = Math.max(1, (max - min) / (n - 1));
   

   这里 (max - min) / (n - 1) 是平均间距，下取整后可能为 0，所以用 Math.max(1, ...) 保个底；

4. 算出桶的个数：

   int bucketCount = (max - min) / bucketSize + 1;
   

5. 为每个桶准备两个数组：

   用 Integer.MAX_VALUE / Integer.MIN_VALUE 当“空桶标记”；

• bucketMin[i]：第 i 个桶里目前最小值
• bucketMax[i]：第 i 个桶里目前最大值

int idx = (num - min) / bucketSize;

• 跳过空桶；
• 当前非空桶的 min - 上一个非空桶的 max，就是一个候选间距；
• 一路维护一个全局最大值。

这样全程都是几次线性扫描，所以是 O(n) 时间、O(n) 空间。

import java.util.Arrays;

publicclassMaxGapSolution{

publicintmaximumGap(int[] nums){
if (nums == null || nums.length < 2) {
return0;
        }

int n = nums.length;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;

// 1. 找到全局最小值和最大值
for (int num : nums) {
if (num < min) {
                min = num;
            }
if (num > max) {
                max = num;
            }
        }

// 所有数都一样
if (min == max) {
return0;
        }

// 2. 计算桶大小和桶数量
int bucketSize = Math.max(1, (max - min) / (n - 1));
int bucketCount = (max - min) / bucketSize + 1;

int[] bucketMin = newint[bucketCount];
int[] bucketMax = newint[bucketCount];
        Arrays.fill(bucketMin, Integer.MAX_VALUE);
        Arrays.fill(bucketMax, Integer.MIN_VALUE);

// 3. 把每个数丢进对应的桶里
for (int num : nums) {
int idx = (num - min) / bucketSize;
            bucketMin[idx] = Math.min(bucketMin[idx], num);
            bucketMax[idx] = Math.max(bucketMax[idx], num);
        }

// 4. 扫描桶，计算最大间距
int prevMax = min;
int maxGap = 0;
for (int i = 0; i < bucketCount; i++) {
// 空桶跳过
if (bucketMin[i] == Integer.MAX_VALUE) {
continue;
            }
// 当前桶最小值和上一个非空桶最大值的差
            maxGap = Math.max(maxGap, bucketMin[i] - prevMax);
            prevMax = bucketMax[i];
        }

return maxGap;
    }

// 简单测一下
publicstaticvoidmain(String[] args){
        MaxGapSolution s = new MaxGapSolution();
        System.out.println(s.maximumGap(newint[]{3, 6, 9, 1})); // 输出 3
        System.out.println(s.maximumGap(newint[]{10}));         // 输出 0
        System.out.println(s.maximumGap(newint[]{1, 1000000})); // 输出 999999
    }
}

这个写完基本就是面试版标准答案了：一个排序版、一个桶版，两种思路都能聊，复杂度也说得清楚。

顺带一提，我前段时间写数据库压测的时候顺手看了下 MySQL 和 Postgres 在不同场景下的表现，里面也大量用到这种“先算范围、再分桶、只存关键统计量”的思路，套路其实是通的。

反正这题你把代码敲两遍，自己画个小例子算一下桶是怎么分的，以后再刷到就是送分题了。

-END-

我为大家打造了一份RPA教程，完全免费：songshuhezi.com/rpa.html