元素差值

最大间距

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

示例1:

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

示例2:

输入: [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。

方案A 基于基数排序找出最大间距

思路: 将数组排序后再找出最大间距

function maximumGap(nums) {
    if(nums.length<2){
        return 0
    }
    let max=Math.max(...nums);
    let maxDigit=String(max).length;
    let range=10;
    for(let i=0,digit=1;i<maxDigit;i++,digit*=10){
        let bucketNums=new Array(range).fill(0).map(value=>new Array());
        for(let j=0;j<nums.length;j++){
            let redix=Math.floor(nums[j]/digit)%10;
            bucketNums[redix].push(nums[j]);
        }
        let index=0;
        for(let j=0;j<range;j++){
            if(bucketNums[j].length){
                for(let k=0;k<bucketNums[j].length;k++){
                    nums[index++]=bucketNums[j][k];
                }
            }
        }
    }
    let diff=0;
    for(let i=1;i<nums.length;i++){
        diff=Math.max(diff,nums[i]-nums[i-1]);
    }
    return diff;
};

性能分析:

• 时间复杂度：O(N)，其中 N 是数组的长度。
• 空间复杂度：O(N)，其中 N 是数组的长度。

最小差值

给你一个整数数组 nums，请你给数组中的每个元素 nums[i] 都加上一个任意数字 x （-k <= x <= k），从而得到一个新数组 result 。

返回数组 result 的最大值和最小值之间可能存在的最小差值。

示例1:

输入：nums = [1], k = 0
输出：0
解释：result = [1]

示例2:

输入：nums = [0,10], k = 2
输出：6
解释：result = [2,8]

思路:A 数组中的每个数可以波动 [-K, K]，其中的最小差值就是 最大值−k 和 最小值+k 的差值，如果差值 <0，则说明每个数字都可以波动成相等的数字，直接返回 0 即可。

function smallestRangeI(nums, k) {
    let max=Math.max(...nums);
    let min=Math.min(...nums);
    return Math.max(0,max-min-2*k);
};

性能分析:

• 时间复杂度: O(N)，其中 N 是 A 的长度。
• 空间复杂度: O(1)