Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Try to solve it in linear time/space.
Return 0 if the array contains less than 2 elements.
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
思路：
这是一道难题，难点在于不能排序，但是要找到在排序的情况下相邻数字的最大差。
各种想不出来，很low的用了排序，居然也通过了。
然后看答案，发现可以很巧妙的利用桶的思想。找到数组里面的最大值和最小值，则数字间隔gap满足：
gap >= (max - min) / (N - 1) 结果向下取整 注意gap = 0 时取 1， 防止后面除0
然后，可以分为 (max - min) / gap + 1 个桶
每个数字根据 (num[i] - min) / gap 来决定放在哪个桶里。
记录每个桶里的最大值和最小值。
则最大间隔不会在桶内，而会在相邻的桶之间，bucket[i].min - bucket[i - 1].max 中最大的数字就是目标数字。
//这个虽然通过了，但是用了排序，是O（nlogn）的算法
int maximumGap(vector<int> &num) {
int ans = ;
sort(num.begin(), num.end());
for(int i = ; i < num.size(); i++)
{
ans = num[i] - num[i - ];
}
return ans;
}
---------------------------------------------------------------------------------
//答案的思路
int maximumGap1(vector<int> &num) {
if(num.size() < ) return ;
//第一步，找最大和最小值
int maxnum = num[];
int minnum = num[];
for(int i = ; i < num.size(); i++)
{
maxnum = (maxnum < num[i]) ? num[i] : maxnum;
minnum = (minnum > num[i]) ? num[i] : minnum;
}
//第二步：判断间隔的大小
int gap = (maxnum - minnum) / (num.size() - );
gap = (gap == ) ? : gap;
//判断和记录每个桶的最大和最小数字
vector<vector<int>> bucket((maxnum - minnum) / gap + , vector<int>(, -)); //只需记录每个桶的最大和最小数字
for(int i = ; i < num.size(); i++)
{
int belong = (num[i] - minnum) / gap;
bucket[belong][] = (num[i] > bucket[belong][]) ? num[i] : bucket[belong][]; //更新最大值
bucket[belong][] = (bucket[belong][] < || num[i] < bucket[belong][]) ? num[i] : bucket[belong][]; //更新最小值
} //找最大间隔
int ans = ;
int pre = ;
for(int i = ; i < bucket.size(); i++)
{
if(bucket[i][] == -) continue;
ans = (bucket[i][] - bucket[pre][] > ans) ? bucket[i][] - bucket[pre][] : ans;
pre = i;
}
return ans;
}
网上还有一种方法是利用基数排序，我还没看。
int maximumGap(std::vector<int> &num) {
for(unsigned bit = ; bit < ; bit++)
std::stable_partition(num.begin(), num.end(), [bit](int a){
return !(a & ( << bit));
});
int difference = ;
for(std::size_t i = ; i < num.size(); i++) {
difference = std::max(difference, num[i] - num[i-]);
}
return difference;
}