Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Return 0 if the array contains less than 2 elements.
Notice
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
Example
Given [1, 9, 2, 5], the sorted form of it is [1, 2, 5, 9], the maximum gap is between 5 and 9 = 4.
分析：http://bookshadow.com/weblog/2014/12/14/leetcode-maximum-gap/
假设有N个元素，最小是A, 最大是B。那么最大差值一定大于interval = (1.0 * max - min) / num.length。
我们需要num.length + 1个桶 (0 to num.length)，令每个bucket（桶）的大小为interval，对于数组中的任意整数K，很容易通过算式loc = (K - A) / interval 找出其桶的位置，然后维护每一个桶的最大值和最小值.
class Solution {
/**
* @param nums:
* an array of integers
* @return: the maximum difference
*/
public int maximumGap(int[] num) {
if (num == null || num.length < ) return ;
int max = num[], min = num[];
for (int i = ; i < num.length; i++) {
max = Math.max(max, num[i]);
min = Math.min(min, num[i]);
}
if (max - min <= ) return max - min;
// the max gap is absolutely greater than (1.0 * max - min) / num.length
// so the interval below can guarantee the maximu gap values in two different buckets.
double interval = (1.0 * max - min) / num.length;
Bucket[] buckets = new Bucket[num.length + ]; // project to (0 - n)
for (int i = ; i < buckets.length; i++) {
buckets[i] = new Bucket();
}
// distribute every number to a bucket array
for (int i = ; i < num.length; i++) {
int index = (int)((num[i] - min) / interval);
if (buckets[index].low == -) {
buckets[index].low = num[i];
buckets[index].high = num[i];
} else {
buckets[index].low = Math.min(buckets[index].low, num[i]);
buckets[index].high = Math.max(buckets[index].high, num[i]);
}
}
// scan buckets to find maximum gap
int result = ;
int prev = buckets[].high;
for (int i = ; i < buckets.length; i++) {
if (buckets[i].low != -) {
result = Math.max(result, buckets[i].low - prev);
prev = buckets[i].high;
}
}
return result;
}
}
class Bucket {
int low;
int high;
public Bucket() {
low = -;
high = -;
}
}