??今天晚上在lintCode上做了一道题，非常的简单，但是这个题有一个挑战项，使得这个问题有一定的难度。
题意：
给定一个未经排序的数组，请找出其排序表中连续两个要素的最大间距。
如果数组中的要素少于 2 个，请返回 0.
样例：
给定数组 [1, 9, 2, 5]，其排序表为 [1, 2, 5, 9]，其最大的间距是在 5 和 9 之间，= 4.
注意事项：
可以假定数组中的所有要素都是非负整数，且最大不超过 32 位整数。
挑战
用排序的方法解决这个问题是比较简单的方法，但是排序的时间复杂度是O(nlogn), 能否使用线性的时间和空间复杂度的方法解决这个问题。
??这个题用常规的方法非常的简单，使用排序排一个序，然后在找到最大间距就行了。但是看到挑战项，这个题就不是那么的简单了。
1.排序方法
??排序方法太简单了，这里就不在解释是怎么回事了。
public int maximumGap(int[] nums) {
// write your code here
Arrays.sort(nums);
int max = 0;
for(int i = 1; i < nums.length; i++){
if(nums[i] - nums[i - 1] > max){
max = nums[i] - nums[i - 1];
}
}
return max;
}
2.线性时间的解法
??这里，我先贴代码，在解释一下，我也不知道能不能解释清楚 ，我只能按照自己的想法来解释。
public int maximumGap(int[] nums) {
if (null == nums || nums.length < 2) {
return 0;
}
int length = nums.length;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < length; i++) {
if (nums[i] < min) {
min = nums[i];
}
if (nums[i] > max) {
max = nums[i];
}
}
//桶的概念
int bucketCapacity = (max - min) / length + 1;
//小桶
int[] minBuckets = new int[length];
//大桶
int[] maxBuckets = new int[length];
int maxDistance = 0;
for (int i = 0; i < length; i++) {
minBuckets[i] = Integer.MAX_VALUE;
maxBuckets[i] = Integer.MIN_VALUE;
}
for (int i = 0; i < length; i++) {
int index = (nums[i] - min) / bucketCapacity;
//小桶装当前位置的最小值
if (minBuckets[index] > nums[i]) {
minBuckets[index] = nums[i];
}
//大桶装当前位置的最大值
if (maxBuckets[index] < nums[i]) {
maxBuckets[index] = nums[i];
}
}
int pre = 0;
for (int i = 1; i < length; i++) {
if (minBuckets[i] == Integer.MAX_VALUE && maxBuckets[i] == Integer.MIN_VALUE)
continue;
if (minBuckets[i] - maxBuckets[pre] > maxDistance) {
//小桶的后一个与大桶的前一个在有序表中肯定相邻
maxDistance = minBuckets[i] - maxBuckets[pre]; // 因为最大间距不可能在一个桶内，否则bucketNumber ＊ maxDistance > length;
}
pre = i;
}
return maxDistance;
}
??首先，我们可以得出每个桶的容量，这个容量值在后面是用来计算每个数在桶中的下标的。
??其次，然后我们更新每个数在小桶中和大桶中的位置的值，其中大桶更新为最大值，小桶更新为最小值。
??最后，我们可以得出的是，小桶的后一个数字和大桶的前一个数字在有序表中肯定相邻。那是因为，我们在取每一个数字在桶中的相对位置时，有可能有多个数字对应到一个位置，而大桶的最大值和小桶中的最小值肯定在有序表中是相邻，前提是大桶的最大值下标与小桶的最小值下下标之间只有空桶(就是没有数字对应到这个范围里面)。想一想，前一个数字尽可能的最大，后一个数字尽可能的最小，那么肯定这两个数字相邻。
