164. Maximum Gap
給定一個整數數組 nums，返回其排序形式中兩個連續元素之間的最大差值。如果數組包含少於兩個元素，則返回 0。
你必須編寫一個在線性時間內運行並使用線性額外空間的算法。
範例：
輸入：nums = [3,6,9,1]
輸出：3
解釋：數組的排序形式是 [1,3,6,9]，其中 (3,6) 或 (6,9) 有最大差值 3。
Python
class Solution:
def maximumGap(self, nums: List[int]) -> int:
if len(nums) < 2:
return 0
# Find the maximum and minimum values in the array
min_val, max_val = min(nums), max(nums)
# Calculate the size of each bucket
bucket_size = max(1, (max_val - min_val) // (len(nums) - 1))
# Initialize buckets
buckets = [[] for _ in range((max_val - min_val) // bucket_size + 1)]
# Put numbers into buckets
for num in nums:
if num == max_val:
buckets[-1].append(num)
else:
index = (num - min_val) // bucket_size
buckets[index].append(num)
# Find the maximum gap
max_gap = 0
prev_max = min_val
for bucket in buckets:
if not bucket:
continue
curr_min, curr_max = min(bucket), max(bucket)
max_gap = max(max_gap, curr_min - prev_max)
prev_max = curr_max
return max_gap
32.84MB, 874ms
C++
class Solution {
public:
int maximumGap(vector<int>& nums) {
int n = nums.size();
if (n < 2) return 0;
// Find the maximum and minimum values in the array
int minVal = *min_element(nums.begin(), nums.end());
int maxVal = *max_element(nums.begin(), nums.end());
// Calculate the size of each bucket
int bucketSize = max(1, (maxVal - minVal) / (n - 1));
// Initialize buckets
vector<vector<int>> buckets((maxVal - minVal) / bucketSize + 1);
// Put numbers into buckets
for (int num : nums) {
if (num == maxVal) {
buckets.back().push_back(num);
} else {
int index = (num - minVal) / bucketSize;
buckets[index].push_back(num);
}
}
// Find the maximum gap
int maxGap = 0;
int prevMax = minVal;
for (const auto& bucket : buckets) {
if (bucket.empty()) continue;
int currMin = *min_element(bucket.begin(), bucket.end());
int currMax = *max_element(bucket.begin(), bucket.end());
maxGap = max(maxGap, currMin - prevMax);
prevMax = currMax;
}
return maxGap;
}
};
136.37MB, 230ms
Javascript
/**
* @param {number[]} nums
* @return {number}
*/
var maximumGap = function(nums) {
const n = nums.length;
if (n < 2) return 0;
// Find the maximum and minimum values in the array
const minVal = Math.min(...nums);
const maxVal = Math.max(...nums);
// Calculate the size of each bucket
const bucketSize = Math.max(1, Math.floor((maxVal - minVal) / (n - 1)));
// Initialize buckets
const buckets = Array.from({ length: Math.floor((maxVal - minVal) / bucketSize) + 1 }, () => []);
// Put numbers into buckets
for (const num of nums) {
if (num === maxVal) {
buckets[buckets.length - 1].push(num);
} else {
const index = Math.floor((num - minVal) / bucketSize);
buckets[index].push(num);
}
}
// Find the maximum gap
let maxGap = 0;
let prevMax = minVal;
for (const bucket of buckets) {
if (bucket.length === 0) continue;
const currMin = Math.min(...bucket);
const currMax = Math.max(...bucket);
maxGap = Math.max(maxGap, currMin - prevMax);
prevMax = currMax;
}
return maxGap;
};
89.26MB, 398ms
