??今天晚上在lintCode上做了一道題，非常的簡(jiǎn)單瘩例，但是這個(gè)題有一個(gè)挑戰(zhàn)項(xiàng)，使得這個(gè)問題有一定的難度。
題意：
給定一個(gè)未經(jīng)排序的數(shù)組驰徊，請(qǐng)找出其排序表中連續(xù)兩個(gè)要素的最大間距。
如果數(shù)組中的要素少于 2 個(gè)堕阔，請(qǐng)返回 0.
樣例：
給定數(shù)組 [1, 9, 2, 5]棍厂，其排序表為 [1, 2, 5, 9]，其最大的間距是在 5 和 9 之間超陆，= 4.
注意事項(xiàng)：
可以假定數(shù)組中的所有要素都是非負(fù)整數(shù)牺弹，且最大不超過 32 位整數(shù)浦马。
挑戰(zhàn)
用排序的方法解決這個(gè)問題是比較簡(jiǎn)單的方法，但是排序的時(shí)間復(fù)雜度是O(nlogn), 能否使用線性的時(shí)間和空間復(fù)雜度的方法解決這個(gè)問題张漂。
??這個(gè)題用常規(guī)的方法非常的簡(jiǎn)單晶默，使用排序排一個(gè)序，然后在找到最大間距就行了航攒。但是看到挑戰(zhàn)項(xiàng)磺陡，這個(gè)題就不是那么的簡(jiǎn)單了。
1.排序方法
??排序方法太簡(jiǎn)單了漠畜，這里就不在解釋是怎么回事了币他。
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.線性時(shí)間的解法
??這里，我先貼代碼憔狞，在解釋一下圆丹，我也不知道能不能解釋清楚 ，我只能按照自己的想法來解釋躯喇。
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;
//小桶裝當(dāng)前位置的最小值
if (minBuckets[index] > nums[i]) {
minBuckets[index] = nums[i];
}
//大桶裝當(dāng)前位置的最大值
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) {
//小桶的后一個(gè)與大桶的前一個(gè)在有序表中肯定相鄰
maxDistance = minBuckets[i] - maxBuckets[pre]; // 因?yàn)樽畲箝g距不可能在一個(gè)桶內(nèi)辫封，否則bucketNumber ＊ maxDistance > length;
}
pre = i;
}
return maxDistance;
}
??首先，我們可以得出每個(gè)桶的容量廉丽，這個(gè)容量值在后面是用來計(jì)算每個(gè)數(shù)在桶中的下標(biāo)的倦微。
??其次，然后我們更新每個(gè)數(shù)在小桶中和大桶中的位置的值正压，其中大桶更新為最大值欣福，小桶更新為最小值。
??最后焦履，我們可以得出的是拓劝，小桶的后一個(gè)數(shù)字和大桶的前一個(gè)數(shù)字在有序表中肯定相鄰。那是因?yàn)榧慰悖覀冊(cè)谌∶恳粋€(gè)數(shù)字在桶中的相對(duì)位置時(shí)郑临，有可能有多個(gè)數(shù)字對(duì)應(yīng)到一個(gè)位置，而大桶的最大值和小桶中的最小值肯定在有序表中是相鄰屑宠，前提是大桶的最大值下標(biāo)與小桶的最小值下下標(biāo)之間只有空桶(就是沒有數(shù)字對(duì)應(yīng)到這個(gè)范圍里面)厢洞。想一想，前一個(gè)數(shù)字盡可能的最大典奉，后一個(gè)數(shù)字盡可能的最小躺翻，那么肯定這兩個(gè)數(shù)字相鄰。
