给定一个数组A及其大小n，求其排序后的相邻两数的最大差值。（注：要求时间复杂度为O(n)）
思路：题目要求对排序后的数组进行操作，显然需要先对数组进行排序。如果没有要求时间复杂度，那么可以有很多种排序算法，如快速排序、堆排序、归并排序等等。但是这里要求时间复杂度为O(n)，就不能用上述常规的排序算法了。
那么桶排序可以吗？由于我们不知道最大数的位数，因此，如果最大数的位数很大的话，我们就需要成千上万个桶，显然对空间要求太大。我们可以利用桶排序的思想，利用它的变种：
1) 首先求出数组的最大值max和最小值min；
2) 然后将该区间均等的划分为n+1份，即n+1个桶，那么由于只有n个数，因此，必定至少有一个桶为空桶；
3) 遍历数组，将所有数入桶，并记录每一个桶的最大值和最小值；
4) 不用考虑桶内数的差值，因为它都不会大过空桶两边的桶的数的差值；
5) 依次遍历每一个桶，找到一个空桶，记录其前一个非空桶的最大值和其后一个非空桶的最小值，它们的差值就是最大的（考虑有多个空桶的情况）。
code：
int maxGap(int A[], int n) { int min = A[0]; int max = A[0]; //找出最大值和最小值 for(int i = 1; i < n; ++i){ min = (min <= A[i] ? min : A[i]); max = (max >= A[i] ? max : A[i]); } int* minArr = new int[n+1]();//记录每个桶中的最小数 int* maxArr = new int[n+1]();//记录每个桶中的最大数 bool hasNum[n+1] = {0};//记录桶中是否有数 for(int i = 0; i < n; ++i){ //求出每一个数所在的桶的编号 int bocketID = bocketNum(a, i, min, max, n); minArr[bocketID] = hasNum[bocketID] ? Min(minArr[bocketID], A[i]) : A[i]; maxArr[bocketID] = hasNum[bocketID] ? Max(maxArr[bocketID], A[i]) : A[i]; hasNum[bocketID] = true; } int MaxGap = 0;//记录最大差值 int LastMax = 0;//记录当前空桶的上一个桶的最大值 int i = 0; while(i < n + 1){ //可能会有多个空桶 //遍历桶，找到一个空桶 while(i < n + 1 && hasNum[i]) i++; if(i == n + 1) break; LastMax = maxArr[i-1]; //继续遍历桶，找到下一个非空桶 while(i < n + 1 && !hasNum[i]) i++; if(i == n + 1) break; MaxGap = Max(MaxGap, minArr[i]-LastMax); } delete []minArr; delete []maxArr; return MaxGap; } //求出每一个数所在的桶的编号 int bocketNum(int a[], int i, int min, int max, int len){ return (a[i]-min) * len / (max-min); } int Min(int a, int b){ return a <= b ? a : b; } int Max(int a, int b){ return a >= b ? a : b; }
