LeetCode 164. 最大间距（桶排序+鸽笼原理）

2020年9月4日 周五 天气晴 【不悲叹过去，不荒废现在，不惧怕未来】

---

本文目录

桶排+鸽笼原理想法代码 参考文献

---

桶排+鸽笼原理

想法

桶的容量 bucketSize = (maxVal - minVal) / (nums.size() - 1)，从数学角度思考，bucketSize 就是 nums 中每相邻两个数差值的平均值 avgGap，而我们要求的是 nums 里相邻两个数的最大差值 maxGap，因此 maxGap >= avgGap = bucketSize。而桶内的区间都是前闭后开的，形如 [min,a)、[b,c)、[d,e)、[f,max)，这样的话，一个桶内的最大间距就小于桶的容量，所以最大间距不会出现在桶内。同时，为了方便编码，生成桶的数量应该要 +1，这样就不需要单独去处理边界值 max 了。

代码

// 建立桶的结构体，桶里只保留最大元素和最小元素 struct Bucket { bool used = false; int maxVal = INT_MIN; int minVal = INT_MAX; }; class Solution { public: int maximumGap(vector<int>& nums) { int len = nums.size(); if(len < 2) return 0; // 求原始数组里的最大值和最小值 int maxVal = *max_element(nums.begin(),nums.end()); int minVal = *min_element(nums.begin(),nums.end()); int bucketSize = (maxVal - minVal) / (len - 1); // 桶的容量，也就是每相邻两个数差值的平均值 if(bucketSize==0) // bucketSize=0说明nums中存在大量重复元素 bucketSize = 1; // 令桶的容量至少为1 int bucketCount = (maxVal - minVal) / bucketSize + 1; // 桶的个数 vector<Bucket> buckets(bucketCount); // 建桶 // 每个桶里只保存最大元素和最小元素 for(auto &num:nums){ int pos = (num - minVal) / bucketSize; buckets[pos].used = true; buckets[pos].maxVal = max(buckets[pos].maxVal,num); buckets[pos].minVal = min(buckets[pos].minVal,num); } int res = 0; int pre = minVal; // 遍历每个桶，最大间距出现在两个桶里的元素差值里 for(int i=0;i<bucketCount;++i){ if(!buckets[i].used) continue; // 当前桶里最小值和前一个桶里最大值的差值可能是nums的最大间距 res = max(res,buckets[i].minVal-pre); // 前一个桶的最大值 pre = buckets[i].maxVal; } return res; } };

时间复杂度：$O\left(n+b\right)\approx O\left(n\right)$ 假设桶的大小为 $b$。线性遍历一遍数组中的元素，复杂度为 $O\left(n\right)$。找到桶之间的最大间距需要线性遍历一遍所有的桶，复杂度为 $O\left(b\right)$。所以总复杂度是线性的。

空间复杂度：$O\left(2\cdot b\right)\approx O\left(b\right)$的额外空间。 每个桶只需要存储最大和最小元素，因此额外空间和桶个数线性相关。

---

参考文献

https://leetcode-cn.com/problems/maximum-gap/solution/cjie-shi-wei-shi-yao-zui-da-jian-ju-bu-hui-chu-xia/ https://leetcode-cn.com/problems/maximum-gap/solution/javacong-bi-jiao-pai-xu-dao-ji-shu-pai-xu-zai-dao-/ https://leetcode-cn.com/problems/maximum-gap/solution/zui-da-jian-ju-by-leetcode/