LeetCode 164: Maximum Gap (Bucket Sort via Pigeonhole Bound)
LeetCode 164SortingBucketPigeonhole PrincipleToday we solve LeetCode 164 - Maximum Gap.
Source: https://leetcode.com/problems/maximum-gap/
English
Problem Summary
Given an integer array nums, return the maximum difference between two successive elements in its sorted form. You must achieve linear time and linear extra space.
Key Insight
Sorting directly costs O(n log n). Instead, use the pigeonhole bound: for n numbers in range [minV, maxV], the average adjacent gap is at least ceil((maxV - minV)/(n - 1)). So the true maximum gap must appear between buckets, not inside one bucket.
Optimal Algorithm Steps
1) Handle small arrays (n < 2) and all-equal values.
2) Compute minV, maxV, and bucket size gap = max(1, (maxV - minV) / (n - 1)).
3) Create buckets storing only bucketMin and bucketMax.
4) Put each value into bucket index (x - minV) / gap.
5) Scan buckets; for every non-empty bucket, update answer with bucketMin[i] - prevMax.
Complexity Analysis
Time: O(n).
Space: O(n).
Common Pitfalls
- Forgetting to guard minV == maxV.
- Using bucket count too small, causing out-of-range index on maxV.
- Trying to compute max gap inside each bucket (wrong place).
- Missing initialization for empty buckets.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int maximumGap(int[] nums) {
int n = nums.length;
if (n < 2) return 0;
int minV = Integer.MAX_VALUE, maxV = Integer.MIN_VALUE;
for (int x : nums) {
minV = Math.min(minV, x);
maxV = Math.max(maxV, x);
}
if (minV == maxV) return 0;
int gap = Math.max(1, (maxV - minV) / (n - 1));
int bucketCount = (maxV - minV) / gap + 1;
int[] bMin = new int[bucketCount];
int[] bMax = new int[bucketCount];
boolean[] used = new boolean[bucketCount];
java.util.Arrays.fill(bMin, Integer.MAX_VALUE);
java.util.Arrays.fill(bMax, Integer.MIN_VALUE);
for (int x : nums) {
int idx = (x - minV) / gap;
used[idx] = true;
bMin[idx] = Math.min(bMin[idx], x);
bMax[idx] = Math.max(bMax[idx], x);
}
int ans = 0;
int prevMax = minV;
for (int i = 0; i < bucketCount; i++) {
if (!used[i]) continue;
ans = Math.max(ans, bMin[i] - prevMax);
prevMax = bMax[i];
}
return ans;
}
}func maximumGap(nums []int) int {
n := len(nums)
if n < 2 {
return 0
}
minV, maxV := nums[0], nums[0]
for _, x := range nums {
if x < minV {
minV = x
}
if x > maxV {
maxV = x
}
}
if minV == maxV {
return 0
}
gap := (maxV - minV) / (n - 1)
if gap < 1 {
gap = 1
}
bucketCount := (maxV-minV)/gap + 1
bMin := make([]int, bucketCount)
bMax := make([]int, bucketCount)
used := make([]bool, bucketCount)
for i := 0; i < bucketCount; i++ {
bMin[i] = 1<<31 - 1
bMax[i] = -1 << 31
}
for _, x := range nums {
idx := (x - minV) / gap
used[idx] = true
if x < bMin[idx] {
bMin[idx] = x
}
if x > bMax[idx] {
bMax[idx] = x
}
}
ans, prevMax := 0, minV
for i := 0; i < bucketCount; i++ {
if !used[i] {
continue
}
if bMin[i]-prevMax > ans {
ans = bMin[i] - prevMax
}
prevMax = bMax[i]
}
return ans
}class Solution {
public:
int maximumGap(vector<int>& nums) {
int n = (int)nums.size();
if (n < 2) return 0;
auto [minIt, maxIt] = minmax_element(nums.begin(), nums.end());
int minV = *minIt, maxV = *maxIt;
if (minV == maxV) return 0;
int gap = max(1, (maxV - minV) / (n - 1));
int bucketCount = (maxV - minV) / gap + 1;
vector<int> bMin(bucketCount, INT_MAX), bMax(bucketCount, INT_MIN);
vector<bool> used(bucketCount, false);
for (int x : nums) {
int idx = (x - minV) / gap;
used[idx] = true;
bMin[idx] = min(bMin[idx], x);
bMax[idx] = max(bMax[idx], x);
}
int ans = 0, prevMax = minV;
for (int i = 0; i < bucketCount; i++) {
if (!used[i]) continue;
ans = max(ans, bMin[i] - prevMax);
prevMax = bMax[i];
}
return ans;
}
};class Solution:
def maximumGap(self, nums: list[int]) -> int:
n = len(nums)
if n < 2:
return 0
min_v, max_v = min(nums), max(nums)
if min_v == max_v:
return 0
gap = max(1, (max_v - min_v) // (n - 1))
bucket_count = (max_v - min_v) // gap + 1
b_min = [float('inf')] * bucket_count
b_max = [float('-inf')] * bucket_count
used = [False] * bucket_count
for x in nums:
idx = (x - min_v) // gap
used[idx] = True
b_min[idx] = min(b_min[idx], x)
b_max[idx] = max(b_max[idx], x)
ans = 0
prev_max = min_v
for i in range(bucket_count):
if not used[i]:
continue
ans = max(ans, b_min[i] - prev_max)
prev_max = b_max[i]
return ansvar maximumGap = function(nums) {
const n = nums.length;
if (n < 2) return 0;
let minV = Infinity, maxV = -Infinity;
for (const x of nums) {
if (x < minV) minV = x;
if (x > maxV) maxV = x;
}
if (minV === maxV) return 0;
const gap = Math.max(1, Math.floor((maxV - minV) / (n - 1)));
const bucketCount = Math.floor((maxV - minV) / gap) + 1;
const bMin = Array(bucketCount).fill(Infinity);
const bMax = Array(bucketCount).fill(-Infinity);
const used = Array(bucketCount).fill(false);
for (const x of nums) {
const idx = Math.floor((x - minV) / gap);
used[idx] = true;
bMin[idx] = Math.min(bMin[idx], x);
bMax[idx] = Math.max(bMax[idx], x);
}
let ans = 0, prevMax = minV;
for (let i = 0; i < bucketCount; i++) {
if (!used[i]) continue;
ans = Math.max(ans, bMin[i] - prevMax);
prevMax = bMax[i];
}
return ans;
};中文
题目概述
给定整数数组 nums，返回其排序后相邻元素差值的最大值。要求时间复杂度线性，额外空间线性。
核心思路
直接排序是 O(n log n)。利用抽屉原理：在范围 [minV, maxV] 内放 n 个数，相邻平均间距至少是 ceil((maxV - minV)/(n - 1))。最大相邻差不会出现在同一桶内部，而会出现在两个非空桶之间。
最优算法步骤
1）处理边界：n < 2 直接返回 0，全部相等也返回 0。
2）计算桶宽 gap = max(1, (maxV - minV) / (n - 1))。
3）每个桶只维护最小值和最大值。
4）把每个数放入索引 (x - minV) / gap 的桶。
5）按桶顺序扫描，用当前桶最小值减去前一非空桶最大值更新答案。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(n)。
常见陷阱
- 漏掉 minV == maxV 的情况。
- 桶数量计算不当导致 maxV 越界。
- 在桶内求最大差（真正答案在桶间）。
- 空桶未正确跳过，导致差值计算错误。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int maximumGap(int[] nums) {
int n = nums.length;
if (n < 2) return 0;
int minV = Integer.MAX_VALUE, maxV = Integer.MIN_VALUE;
for (int x : nums) {
minV = Math.min(minV, x);
maxV = Math.max(maxV, x);
}
if (minV == maxV) return 0;
int gap = Math.max(1, (maxV - minV) / (n - 1));
int bucketCount = (maxV - minV) / gap + 1;
int[] bMin = new int[bucketCount];
int[] bMax = new int[bucketCount];
boolean[] used = new boolean[bucketCount];
java.util.Arrays.fill(bMin, Integer.MAX_VALUE);
java.util.Arrays.fill(bMax, Integer.MIN_VALUE);
for (int x : nums) {
int idx = (x - minV) / gap;
used[idx] = true;
bMin[idx] = Math.min(bMin[idx], x);
bMax[idx] = Math.max(bMax[idx], x);
}
int ans = 0;
int prevMax = minV;
for (int i = 0; i < bucketCount; i++) {
if (!used[i]) continue;
ans = Math.max(ans, bMin[i] - prevMax);
prevMax = bMax[i];
}
return ans;
}
}func maximumGap(nums []int) int {
n := len(nums)
if n < 2 {
return 0
}
minV, maxV := nums[0], nums[0]
for _, x := range nums {
if x < minV {
minV = x
}
if x > maxV {
maxV = x
}
}
if minV == maxV {
return 0
}
gap := (maxV - minV) / (n - 1)
if gap < 1 {
gap = 1
}
bucketCount := (maxV-minV)/gap + 1
bMin := make([]int, bucketCount)
bMax := make([]int, bucketCount)
used := make([]bool, bucketCount)
for i := 0; i < bucketCount; i++ {
bMin[i] = 1<<31 - 1
bMax[i] = -1 << 31
}
for _, x := range nums {
idx := (x - minV) / gap
used[idx] = true
if x < bMin[idx] {
bMin[idx] = x
}
if x > bMax[idx] {
bMax[idx] = x
}
}
ans, prevMax := 0, minV
for i := 0; i < bucketCount; i++ {
if !used[i] {
continue
}
if bMin[i]-prevMax > ans {
ans = bMin[i] - prevMax
}
prevMax = bMax[i]
}
return ans
}class Solution {
public:
int maximumGap(vector<int>& nums) {
int n = (int)nums.size();
if (n < 2) return 0;
auto [minIt, maxIt] = minmax_element(nums.begin(), nums.end());
int minV = *minIt, maxV = *maxIt;
if (minV == maxV) return 0;
int gap = max(1, (maxV - minV) / (n - 1));
int bucketCount = (maxV - minV) / gap + 1;
vector<int> bMin(bucketCount, INT_MAX), bMax(bucketCount, INT_MIN);
vector<bool> used(bucketCount, false);
for (int x : nums) {
int idx = (x - minV) / gap;
used[idx] = true;
bMin[idx] = min(bMin[idx], x);
bMax[idx] = max(bMax[idx], x);
}
int ans = 0, prevMax = minV;
for (int i = 0; i < bucketCount; i++) {
if (!used[i]) continue;
ans = max(ans, bMin[i] - prevMax);
prevMax = bMax[i];
}
return ans;
}
};class Solution:
def maximumGap(self, nums: list[int]) -> int:
n = len(nums)
if n < 2:
return 0
min_v, max_v = min(nums), max(nums)
if min_v == max_v:
return 0
gap = max(1, (max_v - min_v) // (n - 1))
bucket_count = (max_v - min_v) // gap + 1
b_min = [float('inf')] * bucket_count
b_max = [float('-inf')] * bucket_count
used = [False] * bucket_count
for x in nums:
idx = (x - min_v) // gap
used[idx] = True
b_min[idx] = min(b_min[idx], x)
b_max[idx] = max(b_max[idx], x)
ans = 0
prev_max = min_v
for i in range(bucket_count):
if not used[i]:
continue
ans = max(ans, b_min[i] - prev_max)
prev_max = b_max[i]
return ansvar maximumGap = function(nums) {
const n = nums.length;
if (n < 2) return 0;
let minV = Infinity, maxV = -Infinity;
for (const x of nums) {
if (x < minV) minV = x;
if (x > maxV) maxV = x;
}
if (minV === maxV) return 0;
const gap = Math.max(1, Math.floor((maxV - minV) / (n - 1)));
const bucketCount = Math.floor((maxV - minV) / gap) + 1;
const bMin = Array(bucketCount).fill(Infinity);
const bMax = Array(bucketCount).fill(-Infinity);
const used = Array(bucketCount).fill(false);
for (const x of nums) {
const idx = Math.floor((x - minV) / gap);
used[idx] = true;
bMin[idx] = Math.min(bMin[idx], x);
bMax[idx] = Math.max(bMax[idx], x);
}
let ans = 0, prevMax = minV;
for (let i = 0; i < bucketCount; i++) {
if (!used[i]) continue;
ans = Math.max(ans, bMin[i] - prevMax);
prevMax = bMax[i];
}
return ans;
};
Comments