164. 最大间距（bucket桶）

链接164. 最大间距题解164. 最大间距 - 力扣LeetCodeclass Solution { public: int maximumGap(vectorint nums) { int n nums.size(); if (n 2) { return 0; } int minVal *min_element(nums.begin(), nums.end()); int maxVal *max_element(nums.begin(), nums.end()); int d max(1, (maxVal - minVal) / (n - 1)); // 两个桶之间的间隙 int bucketSize (maxVal - minVal) / d 1; // 桶的个数 vectorpairint, int bucket(bucketSize, {-1, -1}); // 存储 (桶内最小值桶内最大值) 对(-1, -1) 表示该桶是空的 for (int i 0; i n; i) { // 需要放入桶的下标 int idx (nums[i] - minVal) / d; // 桶之前没有元素 if (bucket[idx].first -1) { bucket[idx].first bucket[idx].second nums[i]; } else { bucket[idx].first min(bucket[idx].first, nums[i]); bucket[idx].second max(bucket[idx].second, nums[i]); } } int ret 0; int prev -1; // 比较相邻两个有值的桶 for (int i 0; i bucketSize; i) { if (bucket[i].first -1) continue; if (prev ! -1) { ret max(ret, bucket[i].first - bucket[prev].second); } prev i; } return ret; } };怎么理解class Solution { public: int maximumGap(vectorint nums) { int len nums.size(); if (len 2) return 0; int max_value *max_element(nums.begin(), nums.end()); int min_value *min_element(nums.begin(), nums.end()); if (max_value min_value) return 0; // 桶大小 ceil((maxV - minV) / (n-1)) int bucket_size max(1, (int)ceil((double)(max_value - min_value) / (len - 1))); // 桶数量 int bucket_count (max_value - min_value) / bucket_size 1; // 每个桶存储 {最小值, 最大值}初始化为 {INT_MAX, INT_MIN} vectorpairint, int buckets(bucket_count, {INT_MAX, INT_MIN}); for (int num : nums) { int index (num - min_value) / bucket_size; buckets[index].first min(buckets[index].first, num); buckets[index].second max(buckets[index].second, num); } int result 0; int prev_max min_value; for (int i 0; i bucket_count; i) { if (buckets[i].first INT_MAX) continue; // 空桶跳过 // 当前桶的最小值 - 上一个非空桶的最大值 result max(result, buckets[i].first - prev_max); prev_max buckets[i].second; } return result; } };