思路分析
遇到这种考察排序的题目，既然要求线性时间复杂度，那么首先就要往仅有的三种线性时间复杂度排序算法上面去想。回到这个题目本身，是要求数组有序时相邻两个数的最大间隔，我们就要首先考虑，这个“最大间隔”的上下界是怎样的？
显然，如果我们固定数组中的最大值和最小值，则当数组中元素在数轴上面均匀分布时，“最大间隔”取下界，为\(\lceil\frac{A_{max}-A_{min}}{n-1}\rceil\)，其中A为数组，n为数组中元素的个数；而当数组中前n-1个元素连续，最后一个元素与前面相差很远时，“最大间隔”取上界。
此时我们便不难看出，由问题定义，既然当前的无序数组中至少存在一对数字达到所谓的“最大间隔”，它们的差（绝对值）一定大于等于先前“最大间隔”的下界，那么我们只需要按照这个下界即\(\lfloor\frac{A_{max}-A_{min}}{n-1}\rfloor\)，把数组所在的值域切分成n-1个桶，就一定能够保证，这对数字会被分到不同的桶中去——这就是经典的“桶排序”思想！
因此，我们只需要遍历所有的桶，记录当前桶中的最小值与上一个桶中的最大值的差，其中必然有一个会是我们所要找的“最大间隔”。这样，就能够使用线性的时间和空间复杂度来解决这个问题了。
代码
class Solution {
public:
int maximumGap(vector<int> &num) {
if ( num.size() < 2 ) return 0;
int _max = num[0], _min = num[0];
for ( int i = 1; i < num.size(); i++ ) {
_max = max(_max, num[i]);
_min = min(_min, num[i]);
}
int len = (_max - _min) / (num.size() - 1);
if ( !len ) len = 1;
int num_buckets = (_max - _min) / len + 1;
int *max_val = new int[num_buckets];
int *min_val = new int[num_buckets];
bool *flag = new bool[num_buckets];
for ( int i = 0; i < num_buckets; i++ ) {
max_val[i] = INT_MIN;
min_val[i] = INT_MAX;
flag[i] = false;
}
for ( int i = 0; i < num.size(); i++ ) {
int idx = (num[i] - _min) / len;
flag[idx] = true;
max_val[idx] = max(max_val[idx], num[i]);
min_val[idx] = min(min_val[idx], num[i]);
}
vector<int> buckets;
for ( int i = 0; i < num_buckets; i++ ) if ( flag[i] )
buckets.push_back(i);
int ans = INT_MIN;
for ( int i = 0; i < buckets.size() - 1; i++ ) {
ans = max(ans, min_val[buckets[i + 1]] - max_val[buckets[i]]);
}
return ans;
}
};