最大间距
给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0。
示例 1:
输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
示例 2:
输入: [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。
说明:
你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。
请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。
解：
一开始看到这个题目，就觉得有点简单过头，不符合困难的难度，然后就写了如下的代码：
用vector中的内置排序函数sort进行排序后算最大间距。但是sort的排序时间复杂度是nlog2n，所以这样的做法不符合题目要求。
class Solution {
public:
static bool cmp(const int &a,const int &b)
{
return a<b;
}
int maximumGap(vector<int>& nums) {
if(nums.size()<=1)
return 0;
sort(nums.begin(),nums.end(),cmp);
int maxgap=0;
for(int i=1;i<nums.size();i++)
{
maxgap=max(maxgap,nums[i]-nums[i-1]);
}
return maxgap;
}
};
要使得时间复杂度是线性的，要使用桶排序(分区间放元素)：
- 先循环遍历数组获得最大值maxn和最小值minn
- 根据最大值和最小值以及数组容量计算出每个桶的容量size=(maxn-minn)/nums.size()
- 根据容量计算出需要多少个这样的桶num=(maxn-minn)/size+1
- 最后将nums数组中的元素放在对应区间的桶中。
- 最大间距一定是由一个桶的最小值减去上一个桶的最大值(桶中有元素的情况下)
实现代码：
class Solution {
public:
int maximumGap(vector<int>& nums) {
if (nums.size() < 2) return 0;
if (nums.size() == 2) return abs(nums[1] - nums[0]);
int maxn = 0;//存放最大值
int minn = INT_MAX;//存放最小值
for (int i = 0; i < nums.size(); i++)
maxn = max(maxn, nums[i]);
for (int i = 0; i < nums.size(); i++)
minn = min(minn, nums[i]);
if(maxn==minn) return 0;//若相等的话说明数组中存在n个相同数字
int size = (maxn - minn) / nums.size();//区间大小
if(size<1) size=1;//若size小于1说明数组存在很多重复元素
int num = (maxn - minn) / size + 1;//桶的个数
vector<int> nummax(num, 0);//存放桶的最大值
vector<int> nummin(num, maxn);//存放桶的最小值
nummin[0] = minn;
nummax[0] = minn;
nummax[num - 1] = maxn;
nummin[num - 1] = maxn;
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] == maxn || nums[i] == minn)
continue;
int qnum = (nums[i] - minn) / size;//找到放置区间数
nummax[qnum] = max(nummax[qnum], nums[i]);
nummin[qnum] = min(nummin[qnum], nums[i]);
}
for (int i = 0; i < nummin.size(); i++)//删除空桶
{
if (nummax[i] == 0 && nummin[i] == maxn)
{
nummax.erase(nummax.begin() + i);
nummin.erase(nummin.begin() + i);
i--;
}
}
int res = 0;//结果
for (int i = 1; i < nummax.size(); i++)
{
res = max(res, nummin[i] - nummax[i-1]);
}
return res;
}
};