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.
问题：给定一个无序数组，找出数组排序后的相邻元素最大间隔。要求 O(n) 时间复杂度，O(n)空间复杂度
解题思路：
思路一：将所有数组全部排序，再一次遍历求得最大的相邻元素间隔值即可。但是排序算法的最小时间复杂度也需要 O(n*logn) ，无法满足要求。
思路二：题目只需要求出最大相邻间隔，可以利用桶排序，避免求出全部元素大小顺序，而得到结果。时间复杂度降低为 O(n)。
具体思路：
- 将元素全部减去最小值，得到新的数组
- 根据数组长度，创建同样大小的桶（数组表示），并根据数组的数值区间、数组长度得到单个桶的大小
- double bucketSize = (double)(maxv-minv) / (double)nums.size();
- 根据元素大小，将元素放到对应的桶里面。数组中最大值，最小值应该分别在最左边、最右边的两个桶里面。
- int idx = newNums[i] / bucketSize;
- bucket[idx].push_back(newNums[i]);
// 断言 ： 最大间隔值为桶间间隔的最大值。
// 断言证明：当每个桶都有值时，每个桶只有一个值，断言成立。当至少有一个桶为空时，因为最左边、最右边两个桶都有值，则最大间隔必然为桶间间隔，而不是桶内间隔，断言成立。
- 去掉每个桶中最大值、最小值之外的其他值
- 一次遍历求得最大桶间间隔，即为原题解。
int maximumGap(vector<int>& nums) {
if (nums.size() < ) {
return ;
}
int maxv = nums[];
int minv = nums[];
for (int i = ; i < nums.size(); i++) {
maxv = max(maxv, nums[i]);
minv = min(minv, nums[i]);
}
vector<int> newNums;
for (int i = ; i < nums.size(); i++) {
newNums.push_back(nums[i] - minv);
}
vector<vector<int>> bucket(nums.size() + );
double bucketSize = (double)(maxv-minv) / (double)nums.size();
// maxv == minv
if (bucketSize == ) {
return ;
}
for (int i = ; i < newNums.size(); i++) {
int idx = newNums[i] / bucketSize;
bucket[idx].push_back(newNums[i]);
}
for (int i = ; i < bucket.size(); i++) {
if (bucket[i].size() >= ) {
int maxi = bucket[i][];
int mini = bucket[i][];
for (int k = ; k < bucket[i].size(); k++ ) {
maxi = max(maxi, bucket[i][k]);
mini = min(mini, bucket[i][k]);
}
bucket[i] = {mini, maxi};
}
}
int maxgap = ;
int lmaxi = (bucket[].size() == ) ? bucket[][] : bucket[][];
for (int i = ; i < bucket.size(); i++) {
if (bucket[i].size() == ) {
continue;
}
int maxi;
int mini;
if (bucket[i].size() == ) {
maxi = bucket[i][];
mini = bucket[i][];
}else{
// size of bucket[i] shoud be 2;
mini = bucket[i][];
maxi = bucket[i][];
}
if ((mini - lmaxi) > maxgap) {
maxgap = (mini - lmaxi);
}
lmaxi = maxi;
}
return maxgap;
}