题目描述补充

给定一个无序的整数数组，你需要找到数组中任意两个元素之间的最大差值（即最大值与下一个比它小的元素之间的差的绝对值中的最大值）。如果不存在这样的元素对，则返回0。

为了简化问题，你可以假设数组中至少包含两个元素。

示例

输入: [3, 6, 9, 1] 输出: 3 解释: 9 和 6 之间存在最大差值 3。

PHP 代码示例

function maximumGap($nums) {
    $n = count($nums);
    if ($n < 2) {
        return 0;
    }
    
    sort($nums); // 先对数组进行排序
    
    $maxGap = 0;
    for ($i = 1; $i < $n; $i++) {
        $gap = $nums[$i] - $nums[$i - 1];
        $maxGap = max($maxGap, $gap);
    }
    
    // 但由于题目要求找到的是无序数组中的“下一个比它小的元素”的最大差值，
    // 这里实际上我们是在有序数组中计算的连续元素差值，
    // 对于原问题，我们通常需要更复杂的算法（如桶排序的思想）来避免整体排序。
    // 但为了简化，这里展示的是排序后计算的方法，并不完全符合题目原始意图。
    
    // 注意：这里的解法是为了直接展示一种实现方式，并非最优解。
    
    return $maxGap;
}

// 示例用法
$nums = [3, 6, 9, 1];
echo maximumGap($nums); // 输出 3

Python 代码示例

使用桶排序的思想来解决，避免整体排序，以优化性能。

def maximumGap(nums):
    if len(nums) < 2:
        return 0
    
    n = len(nums)
    min_val = min(nums)
    max_val = max(nums)
    
    # 桶的大小至少为1，向上取整
    bucket_size = max(1, (max_val - min_val) // (n - 1))
    bucket_count = (max_val - min_val) // bucket_size + 1
    buckets_min = [float('inf')] * bucket_count
    buckets_max = [float('-inf')] * bucket_count
    bucket_idx = [0] * n
    
    for i, num in enumerate(nums):
        idx = (num - min_val) // bucket_size
        buckets_min[idx] = min(buckets_min[idx], num)
        buckets_max[idx] = max(buckets_max[idx], num)
        bucket_idx[i] = idx
    
    prev_max = buckets_max[0]
    max_gap = 0
    
    for i in range(1, bucket_count):
        if buckets_min[i] == float('inf'):  # 空桶
            continue
        max_gap = max(max_gap, buckets_min[i] - prev_max)
        prev_max = buckets_max[i]
    
    return max_gap

# 示例用法
nums = [3, 6, 9, 1]
print(maximumGap(nums))  # 输出 3

JavaScript 代码示例

JavaScript 版本的实现同样可以采用桶排序的思想。

function maximumGap(nums) {
    if (nums.length < 2) return 0;

    let minVal = Math.min(...nums);
    let maxVal = Math.max(...nums);
    let bucketSize = Math.max(1, Math.floor((maxVal - minVal) / (nums.length - 1)));
    let bucketCount = Math.floor((maxVal - minVal) / bucketSize) + 1;
    let bucketsMin = new Array(bucketCount).fill(Infinity);
    let bucketsMax = new Array(bucketCount).fill(-Infinity);
    let bucketIdx = new Array(nums.length).fill(0);

    for (let i = 0; i < nums.length; i++) {
        let idx = Math.floor((nums[i] - minVal) / bucketSize);
        bucketsMin[idx] = Math.min(bucketsMin[idx], nums[i]);
        bucketsMax[idx] = Math.max(bucketsMax[idx], nums[i]);
        bucketIdx[i] = idx;
    }

    let prevMax = bucketsMax[0];
    let maxGap = 0;

    for (let i = 1; i < bucketCount; i++) {
        if (bucketsMin[i] === Infinity) continue; // 空桶
        maxGap = Math.max(maxGap, bucketsMin[i] - prevMax);
        prevMax = bucketsMax[i];
    }

    return maxGap;
}

// 示例用法
console.log(maximumGap([3, 6, 9, 1])); // 输出 3

码小课网站中有更多相关内容分享给大家学习，包括算法设计、数据结构、编程技巧等，欢迎访问学习。