LeetCode 164. 最大间距

Categories:

题目描述
思路分析
1. 解法一：桶排序思想（推荐）
相似题目

题目描述

✅ 164. 最大间距

思路分析

解法一：桶排序思想（推荐）

核心思路：

最大间距一定出现在相邻桶之间，而不是桶内。

设桶大小 size = max(1, (max-min)/(n-1))，桶数 count。

每个桶维护最小值与最大值，遍历桶间差值取最大。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(n)。

// 桶排序思想求最大间距
class Solution {
    public int maximumGap(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        if (min == max) {
            return 0;
        }

        int n = nums.length;
        int size = Math.max(1, (max - min) / (n - 1));
        int count = (max - min) / size + 1;

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

        for (int num : nums) {
            int idx = (num - min) / size;
            bucketMin[idx] = Math.min(bucketMin[idx], num);
            bucketMax[idx] = Math.max(bucketMax[idx], num);
        }

        int res = 0;
        int prev = min;
        for (int i = 0; i < count; i++) {
            if (bucketMin[i] == Integer.MAX_VALUE) {
                continue;
            }
            res = Math.max(res, bucketMin[i] - prev);
            prev = bucketMax[i];
        }

        return res;
    }
}

// 桶排序思想求最大间距
func maximumGap(nums []int) int {
	if len(nums) < 2 {
		return 0
	}

	minVal, maxVal := nums[0], nums[0]
	for _, v := range nums {
		if v < minVal {
			minVal = v
		}
		if v > maxVal {
			maxVal = v
		}
	}
	if minVal == maxVal {
		return 0
	}

	n := len(nums)
	size := (maxVal - minVal) / (n - 1)
	if size < 1 {
		size = 1
	}
	count := (maxVal-minVal)/size + 1

	bucketMin := make([]int, count)
	bucketMax := make([]int, count)
	for i := 0; i < count; i++ {
		bucketMin[i] = int(^uint(0) >> 1)
		bucketMax[i] = -int(^uint(0)>>1) - 1
	}

	for _, v := range nums {
		idx := (v - minVal) / size
		if v < bucketMin[idx] {
			bucketMin[idx] = v
		}
		if v > bucketMax[idx] {
			bucketMax[idx] = v
		}
	}

	res := 0
	prev := minVal
	for i := 0; i < count; i++ {
		if bucketMin[i] == int(^uint(0)>>1) {
			continue
		}
		gap := bucketMin[i] - prev
		if gap > res {
			res = gap
		}
		prev = bucketMax[i]
	}

	return res
}

相似题目

题目	难度	考察点
912. 排序数组	中等	排序
215. 数组中的第 K 个最大元素	中等	快速选择
324. 摆动排序 II	中等	排序
628. 三个数的最大乘积	简单	排序
274. H 指数	中等	计数/排序
347. 前 K 个高频元素	中等	堆/排序

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/43611748