164. 最大间距

🟠   🔖  数组 桶排序 基数排序 排序  🔗 力扣 LeetCode

题目

Given an integer array nums, return the maximum difference between two successive elements in its sorted form. If the array contains less than two elements, return 0.

You must write an algorithm that runs in linear time and uses linear extra space.

Example 1:

Input: nums = [3,6,9,1]

Output: 3

Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.

Example 2:

Input: nums = [10]

Output: 0

Explanation: The array contains less than 2 elements, therefore return 0.

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9

题目大意

给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0 。

您必须编写一个在「线性时间」内运行并使用「线性额外空间」的算法。

示例 1:

输入: nums = [3,6,9,1]

输出: 3

解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。

示例 2:

输入: nums = [10]

输出: 0

解释: 数组元素个数小于 2，因此返回 0。

提示:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9

解题思路

思路一: 基数排序（Radix Sort）

基数排序是一种线性时间的排序算法，适合用来排序正整数。利用基数排序，可以先对数组进行排序，然后直接遍历排序后的数组计算最大差值。

1. 使用基数排序对数组进行排序。
2. 遍历排序后的数组，计算相邻元素之间的差值，记录最大差值。
3. 返回最大差值。

复杂度分析

• 时间复杂度: O(n)

  • 基数排序：O(n)。
  • 计算最大差值：O(n)。
  • 总时间复杂度为 O(n)。

• 空间复杂度: O(n)，需要额外的缓冲区存储排序结果。

---

思路二: 桶排序（Bucket Sort）

1. 找到数组的最小值和最大值 min 和 max。
2. 计算桶的大小 bucketSize 和数量 bucketCount。
3. 将每个数字分配到桶中，并记录每个桶的最小值和最大值。
4. 遍历所有桶，计算相邻桶之间的差值，记录最大差值。
5. 返回最大差值。

复杂度分析

• 时间复杂度: O(n)

  • 遍历数组分配到桶：O(n)。
  • 遍历桶计算差值：O(k)，其中 k 是桶的数量，最坏情况下 k <= n。
  • 总时间复杂度为 O(n)。

• 空间复杂度: O(n)

  • 使用了 O(k) 的桶存储，最坏情况下 k <= n。

---

思路三: 利用对象的键排序

1. 特殊情况处理：如果数组长度小于 2，则无法计算差值，直接返回 0。

2. 使用对象 obj 去重

• 遍历数组，将每个数字作为对象 obj 的键，以实现数字去重。
• 由于对象的键在 JavaScript 中默认会按照数值顺序排序（对于纯数值键），因此无需显式排序。
• 虽然代码利用了 JavaScript 对象键的特性，但在实现过程中，键值的自动排序并不一定具有线性时间复杂度，因此无法完全保证满足题目对线性时间复杂度的要求。

3. 遍历对象的键，计算最大差值

• 初始化 prev 变量用于记录前一个键值，初始值为 -1（表示尚未遍历任何键）。
• 遍历对象中的键（按数值顺序自动排序），如果 prev 不为 -1，计算当前键与 prev 的差值并更新 maxDiff。
• 遍历完成后，maxDiff 即为相邻数之间的最大差值。

4. 返回计算出的 maxDiff。

复杂度分析

• 时间复杂度: O(n)

  • 遍历数组创建对象的时间复杂度为 O(n)。
  • 遍历对象的键计算最大差值的时间复杂度为 O(k)，其中 k 是对象键的数量。
  • 最坏情况下，键的数量与数组长度相同，因此时间复杂度为 O(n)。

• 空间复杂度: O(n)，需要额外的对象 obj 来存储数组中的唯一元素。

代码

基数排序

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumGap = function (nums) {
	if (nums.length < 2) return 0;

	// 基数排序
	let max = Math.max(...nums),
		exp = 1;
	const n = nums.length,
		buffer = new Array(n);
	while (Math.floor(max / exp) > 0) {
		let count = new Array(10).fill(0);

		for (let num of nums) count[Math.floor(num / exp) % 10]++;
		for (let i = 1; i < 10; i++) count[i] += count[i - 1];
		for (let i = n - 1; i >= 0; i--) {
			const digit = Math.floor(nums[i] / exp) % 10;
			buffer[--count[digit]] = nums[i];
		}
		nums = [...buffer];
		exp *= 10;
	}

	// 计算最大间距
	let maxGap = 0;
	for (let i = 1; i < nums.length; i++) {
		maxGap = Math.max(maxGap, nums[i] - nums[i - 1]);
	}
	return maxGap;
};

桶排序

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumGap = function (nums) {
	if (nums.length < 2) return 0;

	let min = Math.min(...nums),
		max = Math.max(...nums);
	if (min === max) return 0;

	let n = nums.length;
	let bucketSize = Math.max(1, Math.floor((max - min) / (n - 1)));
	let bucketCount = Math.floor((max - min) / bucketSize) + 1;
	let buckets = Array.from({ length: bucketCount }, () => ({
		min: Infinity,
		max: -Infinity
	}));

	// 将数字放入桶中
	for (let num of nums) {
		let idx = Math.floor((num - min) / bucketSize);
		buckets[idx].min = Math.min(buckets[idx].min, num);
		buckets[idx].max = Math.max(buckets[idx].max, num);
	}

	// 计算最大间距
	let maxGap = 0,
		prevMax = min;
	for (let bucket of buckets) {
		if (bucket.min === Infinity) continue; // Skip empty buckets
		maxGap = Math.max(maxGap, bucket.min - prevMax);
		prevMax = bucket.max;
	}

	return maxGap;
};

利用对象的键排序

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumGap = function (nums) {
	if (nums.length < 2) return 0;
	let obj = {};
	for (let num of nums) {
		obj[num] = num;
	}

	let maxDiff = 0,
		prev = -1;

	// 计算最大间距
	for (let key in obj) {
		if (prev == -1) {
			prev = key;
		} else {
			maxDiff = Math.max(maxDiff, key - prev);
			prev = key;
		}
	}
	return maxDiff;
};

相关题目

题号	标题	题解	标签	难度	力扣
1637	两点之间不包含任何点的最宽垂直区域	[✓]	数组 排序	🟢	🀄️ 🔗
2274	不含特殊楼层的最大连续楼层数		数组 排序	🟠	🀄️ 🔗