164. 最大间距
题目描述
输入一个未排序的整数数组 nums。设想把它从小到大排好，求排好后相邻两个元素差值的最大值，并返回。
当数组元素少于 2 个时，返回 0。
算法要在线性时间内完成，额外空间也只能是线性的。
示例 1
输入：nums = [3,6,9,1] 输出：3
解释：排序后为 [1,3,6,9]，相邻差分别是 2、3、3，最大为 3。
示例 2
输入：nums = [10] 输出：0
解释：只有一个元素，返回 0。
数据范围
1 <= nums.length <= 10^50 <= nums[i] <= 10^9
解题思路：桶（鸽笼原理）
设 lo、hi 为最小值和最大值，n 个数之间有 n-1 个间距，它们的和是 hi-lo，所以最大间距至少是平均值 (hi-lo)/(n-1)。把值域切成宽度 size = max(1, (hi-lo)//(n-1)) 的桶，同一个桶内两数之差至多 size-1，不可能是答案。于是只需记录每个桶的最小值和最大值，按桶序扫描：答案就是“当前非空桶的最小值 - 前一个非空桶的最大值”中的最大者。
为什么正确
扫描到桶 b 时，prev 是之前所有元素中的最大值，ans 是这些元素排序后相邻差的最大值。
复杂度分析
时间 O(n)，额外空间 O(n)（桶数不超过 n 左右）。
易错点
桶宽必须向下取整并至少为 1，否则 hi-lo 小于 n-1 时会除以 0；桶内间距一定小于平均间距，所以只比较相邻非空桶之间的差，不要忘了跳过空桶时保留 prev。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def maximumGap(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return 0
lo, hi = min(nums), max(nums)
size = max(1, (hi - lo) // (n - 1))
cnt = (hi - lo) // size + 1
bmin = [None] * cnt
bmax = [None] * cnt
for x in nums:
b = (x - lo) // size
bmin[b] = x if bmin[b] is None else min(bmin[b], x)
bmax[b] = x if bmax[b] is None else max(bmax[b], x)
ans, prev = 0, lo
for b in range(cnt):
if bmin[b] is not None:
ans = max(ans, bmin[b] - prev)
prev = bmax[b]
return ansclass Solution {
public int maximumGap(int[] nums) {
int n = nums.length;
if (n < 2) {
return 0;
}
int lo = Arrays.stream(nums).min().getAsInt(), hi = Arrays.stream(nums).max().getAsInt();
int size = Math.max(1, (hi - lo) / (n - 1));
int cnt = (hi - lo) / size + 1;
int[] bmin = new int[cnt];
int[] bmax = new int[cnt];
Arrays.fill(bmin, Integer.MAX_VALUE);
Arrays.fill(bmax, Integer.MIN_VALUE);
for (int x : nums) {
int b = (x - lo) / size;
bmin[b] = Math.min(bmin[b], x);
bmax[b] = Math.max(bmax[b], x);
}
int ans = 0, prev = lo;
for (int b = 0; b < cnt; b++) {
if (bmin[b] != Integer.MAX_VALUE) {
ans = Math.max(ans, bmin[b] - prev);
prev = bmax[b];
}
}
return ans;
}
}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());
int size = max(1, (hi - lo) / (n - 1));
int cnt = (hi - lo) / size + 1;
vector<int> bmin(cnt, INT_MAX);
vector<int> bmax(cnt, INT_MIN);
for (int x : nums) {
int b = (x - lo) / size;
bmin[b] = min(bmin[b], x);
bmax[b] = max(bmax[b], x);
}
int ans = 0, prev = lo;
for (int b = 0; b < cnt; b++) {
if (bmin[b] != INT_MAX) {
ans = max(ans, bmin[b] - prev);
prev = bmax[b];
}
}
return ans;
}
};func maximumGap(nums []int) int {
n := len(nums)
if n < 2 {
return 0
}
lo, hi := slices.Min(nums), slices.Max(nums)
size := max(1, (hi-lo)/(n-1))
cnt := (hi-lo)/size + 1
bmin := make([]int, cnt)
bmax := make([]int, cnt)
for b := range bmin {
bmin[b] = math.MaxInt
bmax[b] = math.MinInt
}
for _, x := range nums {
b := (x - lo) / size
bmin[b] = min(bmin[b], x)
bmax[b] = max(bmax[b], x)
}
ans, prev := 0, lo
for b := 0; b < cnt; b++ {
if bmin[b] != math.MaxInt {
ans = max(ans, bmin[b]-prev)
prev = bmax[b]
}
}
return ans
}var maximumGap = function(nums) {
const n = nums.length;
if (n < 2) {
return 0;
}
const lo = Math.min(...nums), hi = Math.max(...nums);
const size = Math.max(1, Math.floor((hi - lo) / (n - 1)));
const cnt = Math.floor((hi - lo) / size) + 1;
const bmin = new Array(cnt).fill(null);
const bmax = new Array(cnt).fill(null);
for (const x of nums) {
const b = Math.floor((x - lo) / size);
bmin[b] = bmin[b] === null ? x : Math.min(bmin[b], x);
bmax[b] = bmax[b] === null ? x : Math.max(bmax[b], x);
}
let ans = 0, prev = lo;
for (let b = 0; b < cnt; b++) {
if (bmin[b] !== null) {
ans = Math.max(ans, bmin[b] - prev);
prev = bmax[b];
}
}
return ans;
};function maximumGap(nums: number[]): number {
const n = nums.length;
if (n < 2) {
return 0;
}
const lo = Math.min(...nums), hi = Math.max(...nums);
const size = Math.max(1, Math.floor((hi - lo) / (n - 1)));
const cnt = Math.floor((hi - lo) / size) + 1;
const bmin: (number | null)[] = new Array(cnt).fill(null);
const bmax: (number | null)[] = new Array(cnt).fill(null);
for (const x of nums) {
const b = Math.floor((x - lo) / size);
bmin[b] = bmin[b] === null ? x : Math.min(bmin[b]!, x);
bmax[b] = bmax[b] === null ? x : Math.max(bmax[b]!, x);
}
let ans = 0, prev = lo;
for (let b = 0; b < cnt; b++) {
if (bmin[b] !== null) {
ans = Math.max(ans, bmin[b]! - prev);
prev = bmax[b]!;
}
}
return ans;
}其他解法
基数排序先完整排序再找最大差；桶法利用最大间距不小于平均间距，只比较相邻非空桶的边界，不用完整排序。
解法 2：基数排序 时间 O(d·n)，空间 O(n)
从个位开始，按当前位的数字做一次稳定的计数排序，再处理十位、百位，直到超过最大值的位数 d。排好序后扫描相邻元素，取差值的最大值。
思路是“先线性时间排序再扫描”，容易理解。值域不超过 10⁹ 时 d 至多为 10，常数比桶法大，并且只适用于非负整数。
from typing import List
class Solution:
def maximumGap(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return 0
a = list(nums)
buf = [0] * n
mx = max(a)
exp = 1
while mx >= exp:
cnt = [0] * 10
for x in a:
cnt[x // exp % 10] += 1
for d in range(1, 10):
cnt[d] += cnt[d - 1]
for i in range(n - 1, -1, -1):
d = a[i] // exp % 10
cnt[d] -= 1
buf[cnt[d]] = a[i]
a, buf = buf, a
exp *= 10
return max(a[i] - a[i - 1] for i in range(1, n))class Solution {
public int maximumGap(int[] nums) {
int n = nums.length;
if (n < 2) return 0;
int[] a = nums.clone(), buf = new int[n];
int mx = Arrays.stream(a).max().getAsInt();
for (long exp = 1; mx >= exp; exp *= 10) {
int[] cnt = new int[10];
for (int x : a) cnt[(int) (x / exp % 10)]++;
for (int d = 1; d < 10; d++) cnt[d] += cnt[d - 1];
for (int i = n - 1; i >= 0; i--) {
int d = (int) (a[i] / exp % 10);
buf[--cnt[d]] = a[i];
}
int[] t = a; a = buf; buf = t;
}
int ans = 0;
for (int i = 1; i < n; i++) ans = Math.max(ans, a[i] - a[i - 1]);
return ans;
}
}class Solution {
public:
int maximumGap(vector<int>& nums) {
int n = nums.size();
if (n < 2) return 0;
vector<int> a(nums), buf(n);
int mx = *max_element(a.begin(), a.end());
for (long long exp = 1; mx >= exp; exp *= 10) {
int cnt[10] = {0};
for (int x : a) cnt[x / exp % 10]++;
for (int d = 1; d < 10; d++) cnt[d] += cnt[d - 1];
for (int i = n - 1; i >= 0; i--) {
int d = a[i] / exp % 10;
buf[--cnt[d]] = a[i];
}
swap(a, buf);
}
int ans = 0;
for (int i = 1; i < n; i++) ans = max(ans, a[i] - a[i - 1]);
return ans;
}
};func maximumGap(nums []int) int {
n := len(nums)
if n < 2 {
return 0
}
a := append([]int(nil), nums...)
buf := make([]int, n)
mx := slices.Max(a)
for exp := 1; mx >= exp; exp *= 10 {
cnt := [10]int{}
for _, x := range a {
cnt[x/exp%10]++
}
for d := 1; d < 10; d++ {
cnt[d] += cnt[d-1]
}
for i := n - 1; i >= 0; i-- {
d := a[i] / exp % 10
cnt[d]--
buf[cnt[d]] = a[i]
}
a, buf = buf, a
}
ans := 0
for i := 1; i < n; i++ {
ans = max(ans, a[i]-a[i-1])
}
return ans
}var maximumGap = function(nums) {
const n = nums.length;
if (n < 2) return 0;
let a = nums.slice(), buf = new Array(n).fill(0);
const mx = Math.max(...a);
for (let exp = 1; mx >= exp; exp *= 10) {
const cnt = new Array(10).fill(0);
for (const x of a) cnt[Math.floor(x / exp) % 10]++;
for (let d = 1; d < 10; d++) cnt[d] += cnt[d - 1];
for (let i = n - 1; i >= 0; i--) {
const d = Math.floor(a[i] / exp) % 10;
buf[--cnt[d]] = a[i];
}
[a, buf] = [buf, a];
}
let ans = 0;
for (let i = 1; i < n; i++) ans = Math.max(ans, a[i] - a[i - 1]);
return ans;
};function maximumGap(nums: number[]): number {
const n = nums.length;
if (n < 2) return 0;
let a = nums.slice(), buf: number[] = new Array(n).fill(0);
const mx = Math.max(...a);
for (let exp = 1; mx >= exp; exp *= 10) {
const cnt: number[] = new Array(10).fill(0);
for (const x of a) cnt[Math.floor(x / exp) % 10]++;
for (let d = 1; d < 10; d++) cnt[d] += cnt[d - 1];
for (let i = n - 1; i >= 0; i--) {
const d = Math.floor(a[i] / exp) % 10;
buf[--cnt[d]] = a[i];
}
[a, buf] = [buf, a];
}
let ans = 0;
for (let i = 1; i < n; i++) ans = Math.max(ans, a[i] - a[i - 1]);
return ans;
};