当前位置： 面试刷题>> 数组中最大的差值 (经典算法题500道)
### 题目描述补充
给定一个无序的整数数组，你需要找到数组中任意两个元素之间的最大差值（即最大值与下一个比它小的元素之间的差的绝对值中的最大值）。如果不存在这样的元素对，则返回0。
为了简化问题，你可以假设数组中至少包含两个元素。
### 示例
输入: [3, 6, 9, 1]
输出: 3
解释: 9 和 6 之间存在最大差值 3。
### PHP 代码示例
```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 代码示例
使用桶排序的思想来解决，避免整体排序，以优化性能。
```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 版本的实现同样可以采用桶排序的思想。
```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
```
码小课网站中有更多相关内容分享给大家学习，包括算法设计、数据结构、编程技巧等，欢迎访问学习。