BiruLyu
8/4/2017 - 10:34 PM

## 164. Maximum Gap(#).java

``````public class Solution {
public int maximumGap(int[] nums) {
if (nums.length < 2) return 0;

int n = nums.length;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;

for (int num : nums) {
min = Math.min(min, num);
max = Math.max(max, num);
}

if (min == max) return 0;

int[] minbucket = new int[n];
int[] maxbucket = new int[n];
Arrays.fill(maxbucket, Integer.MIN_VALUE);
Arrays.fill(minbucket, Integer.MAX_VALUE);
int gap = (int)Math.ceil((double)(max-min) / (n-1));  // gap is no smaller than ...
for (int num : nums) {
int i = (num-min)/gap;
minbucket[i] = Math.min(minbucket[i], num);
maxbucket[i] = Math.max(maxbucket[i], num);
}

int res = gap;
for (int i = 0; i < n; i++) {
if (minbucket[i] == Integer.MAX_VALUE) continue;
res = Math.max(res, minbucket[i] - min);
min = maxbucket[i];
}

return res;
}
}``````
``````public class Solution {
public int maximumGap(int[] nums) {
int n = nums.length;
if(n<2){
return 0;
}
if(n==2){
return Math.abs(nums[0]-nums[1]);
}
int max=nums[0],min=nums[0];
for(int num:nums){
if(num>max){
max=num;
}else if(num<min){
min=num;
}
}
if(max==min){
return 0;
}
int steps = (max-min+n-1)/(n-1);
int[] maxs = new int[n], mins = new int[n];
for(int i=0; i<n; i++){
mins[i] = Integer.MAX_VALUE;
}
int idx;
for(int num:nums){
idx = (num-min)/steps;
if(num>maxs[idx]){
maxs[idx]=num;
}
if(num<mins[idx]){
mins[idx]=num;
}
}
int last=maxs[0], maxGap=0;
for(int i=1;i<n;i++){
if(mins[i]==Integer.MAX_VALUE){
continue;
}
if(mins[i]-last>maxGap){
maxGap = mins[i]-last;
}
last = maxs[i];
}
return maxGap;
}
}``````
``````class Bucket{
int low;
int high;
public Bucket(){
low = -1;
high = -1;
}
}

public class Solution {
public int maximumGap(int[] num) {
if(num == null || num.length < 2){
return 0;
}

int max = num[0];
int min = num[0];
for(int i=1; i<num.length; i++){
max = Math.max(max, num[i]);
min = Math.min(min, num[i]);
}

// initialize an array of buckets
Bucket[] buckets = new Bucket[num.length+1]; //project to (0 - n)
for(int i=0; i<buckets.length; i++){
buckets[i] = new Bucket();
}

double interval = (double) num.length / (max - min);
//distribute every number to a bucket array
for(int i=0; i<num.length; i++){
int index = (int) ((num[i] - min) * interval);

if(buckets[index].low == -1){
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 = 0;
int prev = buckets[0].high;
for(int i=1; i<buckets.length; i++){
if(buckets[i].low != -1){
result = Math.max(result, buckets[i].low-prev);
prev = buckets[i].high;
}

}

return result;
}
}``````