最大间距 图解题解

这道题到底在问什么

输入

nums=[3,6,9,1]

输出

3　（排序后 [1,3,6,9]，相邻差 2,3,3，最大 3）

输入

nums=[10]

输出

0　（不足两个元素，没有相邻对）

输入

nums=[1,100]

输出

99　（只有一个间距）

最优解：一步一步想明白

1. 3记住这句：答案藏在「相邻非空桶之间」，桶内差值永远不够大。下面每一帧都在套它。
2. 4先定桶：最小 1、最大 9、共 5 个数，算出桶宽 size=2、桶数 5。每个桶只存它见过的最小值和最大值。
3. 5看第 0 个数 1（紫色）：用 (1-1)/2 算出它该进桶0。
4. 61 落进桶0，这桶刚被点亮，min 和 max 都先记成 1。
5. 7看第 1 个数 3（紫色）：用 (3-1)/2 算出它该进桶1。
6. 83 落进桶1，这桶刚被点亮，min 和 max 都先记成 3。
7. 9看第 2 个数 6（紫色）：用 (6-1)/2 算出它该进桶2。
8. 106 落进桶2，这桶刚被点亮，min 和 max 都先记成 6。
9. 11看第 3 个数 9（紫色）：用 (9-1)/2 算出它该进桶4。
10. 129 落进桶4，这桶刚被点亮，min 和 max 都先记成 9。
11. 13看第 4 个数 4（紫色）：用 (4-1)/2 算出它该进桶1。
12. 144 也落进桶1，刷新这桶的 min=3、max=4。同桶内差值最多 1，不可能是答案。
13. 15所有数都入桶了。现在从左到右扫每个非空桶，只比「上一非空桶的 max」和「当前桶的 min」这一段距离。prev 起步用最小值 1。
14. 16轮到非空桶0（紫框）。跨桶间距 = 本桶最小 1 减去上一非空桶的 max 1，得 0。
15. 170 没超过当前最大间距 0，ans 不变。prev 推进到本桶 max 1。
16. 18轮到非空桶1（紫框）。跨桶间距 = 本桶最小 3 减去上一非空桶的 max 1，得 2。
17. 192 比之前的最大间距大，刷新 ans=2。再把 prev 推到本桶 max 4，准备比下一个非空桶。
18. 20轮到非空桶2（紫框）。跨桶间距 = 本桶最小 6 减去上一非空桶的 max 4，得 2。
19. 212 没超过当前最大间距 2，ans 不变。prev 推进到本桶 max 6。
20. 22桶3 是空的（紫框）。空桶直接跳过，不参与比较，prev 保持 6。空桶的存在正说明这里有一道大缝隙。
21. 23轮到非空桶4（紫框）。跨桶间距 = 本桶最小 9 减去上一非空桶的 max 6，得 3。
22. 243 比之前的最大间距大，刷新 ans=3。再把 prev 推到本桶 max 9，准备比下一个非空桶。
23. 25回头验证：把数排好是 [1, 3, 4, 6, 9]，相邻差里最大的正是 3。我们没真排序，只靠扫桶就 O(n) 得到了它。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return 0
        lo, hi = min(nums), max(nums)
        if lo == hi:
            return 0
        size = max(1, (hi - lo) // (n - 1))
        cnt = (hi - lo) // size + 1
        bmin = [10**20] * cnt
        bmax = [-(10**20)] * cnt
        used = [False] * cnt
        for x in nums:
            i = (x - lo) // size
            bmin[i] = min(bmin[i], x)
            bmax[i] = max(bmax[i], x)
            used[i] = True
        ans, prev = 0, lo
        for i in range(cnt):
            if not used[i]:
                continue
            ans = max(ans, bmin[i] - prev)
            prev = bmax[i]
        return ans

#include <algorithm>
#include <climits>
#include <vector>
using namespace std;
class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return 0;
        int lo = *min_element(nums.begin(), nums.end()), hi = *max_element(nums.begin(), nums.end());
        if (lo == hi) return 0;
        int size = max(1, (hi - lo) / (n - 1));
        int cnt = (hi - lo) / size + 1;
        vector<int> bmin(cnt, INT_MAX), bmax(cnt, INT_MIN);
        vector<bool> used(cnt);
        for (int x : nums) {
            int i = (x - lo) / size;
            bmin[i] = min(bmin[i], x); bmax[i] = max(bmax[i], x); used[i] = true;
        }
        int ans = 0, prev = lo;
        for (int i = 0; i < cnt; ++i) if (used[i]) {
            ans = max(ans, bmin[i] - prev);
            prev = bmax[i];
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int maximumGap(int[] nums) {
        int n = nums.length;
        if (n < 2) return 0;
        int lo = nums[0], hi = nums[0];
        for (int x : nums) { lo = Math.min(lo, x); hi = Math.max(hi, x); }
        if (lo == hi) return 0;
        int size = Math.max(1, (hi - lo) / (n - 1));
        int cnt = (hi - lo) / size + 1;
        int[] bmin = new int[cnt], bmax = new int[cnt];
        boolean[] used = new boolean[cnt];
        Arrays.fill(bmin, Integer.MAX_VALUE);
        Arrays.fill(bmax, Integer.MIN_VALUE);
        for (int x : nums) {
            int i = (x - lo) / size;
            bmin[i] = Math.min(bmin[i], x);
            bmax[i] = Math.max(bmax[i], x);
            used[i] = true;
        }
        int ans = 0, prev = lo;
        for (int i = 0; i < cnt; i++) if (used[i]) {
            ans = Math.max(ans, bmin[i] - prev);
            prev = bmax[i];
        }
        return ans;
    }
}

复杂度

面试官可能追问