最大间距（164）

题目

给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。

如果数组元素个数小于 2，则返回 0。

示例

输入: [3,6,9,1] 输出: 3

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

输入: [10] 输出: 0

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

说明

你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。 请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。

算法

基数排序

先使用基数排序从小到大排序数组，然后再两两比较相邻的数字的最大间距

export const maximumGap = (nums) => {
	const maxDigit = Math.max(...nums).toString().length;
	for (let i = 0, unit = 10, base = 1; i < maxDigit; i++, unit *= 10, base *= 10) {
		const buckets = [];
		nums.forEach((item) => {
			const index = ~~((item % unit) / base);
			buckets[index] ? buckets[index].push(item) : (buckets[index] = [item]);
		});
		let numsIndex = 0;
		buckets.forEach((item) => {
			while (item.length) nums[numsIndex++] = item.shift();
		});
	}
	let maxGap = 0;
	for (let i = 0; i < nums.length - 1; i++) {
		maxGap = Math.max(maxGap, nums[i + 1] - nums[i]);
	}
	return maxGap;
};

桶排序

首先我们要明确：最大间距一定不小于[(max-min)/(nums.length-1)]

所以我们以~~[(max-min)/(nums.length-1)]为桶大小（桶大小最小不能小于1）， 以~~((max-min)/(桶大小))+1为桶数，建立一组桶，然后按照每一个数字距离min的距离放在合适的桶中，我们在每个桶中维护一个长度为2的数组：第一个元素为应该放在这个桶中的最小值；第二个元素为应该放在这个桶中的最大值

设置完桶之后，我们遍历桶，在相邻的不为空的桶中寻找间距（即后一个桶中的第一个元素和前一个桶中的第二个元素）的最大值

export const maximumGap = (nums) => {
	const n = nums.length;
	if (n < 2) return 0;
	const minVal = Math.min(...nums);
	const maxVal = Math.max(...nums);
	const d = Math.max(1, Math.floor(maxVal - minVal) / (n - 1));
	const bucketSize = Math.floor((maxVal - minVal) / d) + 1;
	const bucket = new Array(bucketSize).fill(0).map(() => []);
	for (let i = 0; i < n; i++) {
		const idx = Math.floor((nums[i] - minVal) / d);
		if (bucket[idx].length) {
			bucket[idx][0] = Math.min(bucket[idx][0], nums[i]);
			bucket[idx][1] = Math.max(bucket[idx][1], nums[i]);
		} else {
			bucket[idx].push([nums[i]], [nums[i]]);
		}
	}
	let ret = 0;
	let prev = 0;
	for (let i = 0; i < bucketSize; i++) {
		if (bucket[i].length) {
			ret = Math.max(ret, bucket[i][0] - bucket[prev][1]);
			prev = i;
		}
	}
	return ret;
};