Maximum Gap

Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Try to solve it in linear time/space.
Return 0 if the array contains less than 2 elements.
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

Naive Way: 最初的想法是如果能排序，就能一次遍历求得最大gap，但是排序就是O(nlogn)了。要求在O(n)的时间内做出，唯一能利用的就是O(n)的space了。考虑最坏的情况是所有数字都具有相同间隔，比如[1 3 5 7 9]，在不改变区间范围的情况下，任意改变其中某个数都会使结果变大，也就是说，如果能确定数组的区间范围，(max-min)/size 就是最差的情况，任意有数不是在分割点上，说明本该在那个分割点上的数改变了，max gap也就改变了。

举个例子说明：[1,4,5,7,9]
最大是1，最小是9，一共5个数。5个数应该有4个分区，(平均分)。然后遍历一遍数组将每个数字归入自己所在分区。

[1,3)-> 最小值是1，最大值是1。
[3,5)-> 最小值是4，最大值是4。
[5,7)-> 最小值是5，最大值是5。
[7,9]-> 最小值是7，最大值是9。

这样就可以知道一旦某一区段最小值不是区段下限，就可以知道max gap 可能由它产生。遍历一遍区段，一旦有以上情况就要左右追溯，找出可能的max gap。

算法复杂度可以达到O(n)， space O(n)。

public class Solution {
    public int maximumGap(int[] num) {
        int maxGap = 0;
        // edge case
        if(num.length < 2) return maxGap;
        // find min and max
        int min = num[0], max = min;
        for(int i = 1;i < num.length;i++){
            min = Math.min(min,num[i]);
            max = Math.max(max,num[i]);
        }
        // form gaps
        int dis = (max-min)/(int)Math.min(max-min,num.length-1);
        List<List<Integer>> gaps = new ArrayList<List<Integer>>();
        for(int i = 0;i < (max-min)/dis;i++){
            List<Integer> gap = new ArrayList<Integer>();
            gap.add(-1);
            gap.add(-1);
            gaps.add(gap);
        }
        // fill in gaps
        for(int i = 0;i < num.length;i++){
            List<Integer> gap = gaps.get((int)Math.min(gaps.size()-1,(num[i]-min)/dis));
            if(gap.get(0)==-1)  gap.set(0,num[i]);
            else gap.set(0,Math.min(num[i],gap.get(0)));
            if(gap.get(1)==-1) gap.set(1,num[i]);
            else gap.set(1,Math.max(num[i],gap.get(1)));
        }
        // find maximum gap
        for(int i = 0;i < gaps.size();i++){
            List<Integer> gap = gaps.get(i);
            if(gap.get(0)==-1) continue; // means current gap is empty
            
            int j = i-1;
            // traversal lower level gaps
            while(j >= 0 && gaps.get(j).get(1)==-1) j--;
            if(j>=0) maxGap = Math.max(maxGap, gap.get(0)-gaps.get(j).get(1));
            
            // traversal upper level gaps
            j = i+1;
            while(j < gaps.size() && gaps.get(j).get(0)==-1) j++;
            if(j<gaps.size()) maxGap = Math.max(maxGap, gaps.get(j).get(0)-gap.get(1));
            
            // edge case for one gap
            maxGap = Math.max(maxGap, gap.get(1)-gap.get(0));
        }
        return maxGap;
    }
    
}


Improved Way:这种方法原来叫做bucket sort，原是一种排序的算法，特别适合用来求Gap。Discuss里无一例外全是这种方法，但是施行的也有好有坏，写得最好的我觉得是下面这个。

来自leetcode用户liaison ，使用了数组来存gap，连续的两个位置表示一个bucket。

public int maximumGap(int[] num) {
    if(num.length < 2){
        return 0;
    }

    // Find the min and max elements in the list.
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for(int e : num){
        min = Math.min(e, min);
        max = Math.max(e, max);
    }

    // Put the n elements into (n-1) buckets.
    double div = (max-min)*1.0/(num.length-1);

    // bucket[i]  : min value in the bucket i/2;
    // bucket[i+1]: max value in the bucket i/2;
    // Note: the elements are all non-negatives.
    int [] bucket = new int[num.length*2];
    for(int e : num){
        int i = (int)((e-min)/div) * 2;

        bucket[i]   = bucket[i] == 0 ? e : Math.min(e, bucket[i]);
        bucket[i+1] = bucket[i+1] == 0 ? e : Math.max(e, bucket[i+1]);
    }

    // Calculate the maximum distance between buckets,
    //  which is aslo the maximum gap between elements.
    int last_bound = min;
    int max_gap = Integer.MIN_VALUE;
    for(int i=0; i<num.length*2; i+=2){
        if(bucket[i] == 0){
            // no element in this bucket.
            continue;
        }

        max_gap = Math.max(bucket[i]-last_bound, max_gap);
        last_bound = bucket[i+1];
    }

    return max_gap;
}