package problems;

import java.util.ArrayList;
import java.util.List;

public class MaximumGap {

    class Bucket {
        int min, max, count;

        Bucket() {
            count = 0;
        }

        public void add(int t) {
            if (count == 0)
                min = max = t;
            else {
                min = Math.min(min, t);
                max = Math.max(max, t);
            }
            count++;
        }
    }

    public int maximumGap(int[] num) {
        if (num == null || num.length == 0)
            return 0;

        int N = num.length, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int t : num) {
            min = Math.min(min, t);
            max = Math.max(max, t);
        }

        List<Bucket> Bu = new ArrayList<Bucket>(N - 1);
        for (int i = 0; i < N - 1; i++)
            Bu.add(new Bucket());
        for (int t : num) {
            if (t != min && t != max)
                Bu.get().add(t);
        }
        int gap = Math.max(Bu.get(0).min - min, max - Bu.get(N - 2).max);
        for (int i = 0; i < N - 1; i++)
            gap = Math.max()
    }

    public static void main(String[] args) {
        MaximumGap mg = new MaximumGap();
        int[] num = { 2, 99999999 };
        System.out.println(mg.maximumGap(num));
    }
}

@@ -16,60 +16,8 @@
 s;%0A%0A
-import java.util.ArrayList;%0Aimport java.util.List;%0A%0A
 publ
@@ -82,15 +82,8 @@
  max
-, count
 ;%0A%0A 
@@ -96,16 +96,21 @@
  Bucket(
+int t
 ) %7B%0A    
@@ -121,17 +121,21 @@
     
-count = 0
+min = max = t
 ;%0A  
@@ -180,90 +180,8 @@
 ) %7B%0A
-            if (count == 0)%0A                min = max = t;%0A            else %7B%0A    
     
@@ -204,36 +204,32 @@
 th.min(min, t);%0A
-    
             max 
@@ -252,43 +252,8 @@
 t);%0A
-            %7D%0A            count++;%0A
     
@@ -559,25 +559,24 @@
       %7D%0A
-%0A
         
 List%3CBuc
@@ -571,115 +571,75 @@
     
-List%3CBucket%3E Bu = new ArrayList%3CBucket%3E(N - 1);%0A        for (int i = 0; i %3C N - 1; i++)%0A            Bu.add(
+double D = 1.0 * (max - min - 2) / (N - 1);%0A%0A        Bucket%5B%5D Bu = 
 new 
@@ -648,11 +648,11 @@
 cket
-())
+%5BN%5D
 ;%0A  
@@ -714,16 +714,18 @@
  != max)
+ %7B
 %0A       
@@ -737,16 +737,177 @@
     
-Bu.get()
+int k = (int) Math.floor((t - min - 1) / D);%0A                if (Bu%5Bk%5D == null)%0A                    Bu%5Bk%5D = new Bucket(t);%0A                else%0A                    Bu%5Bk%5D
 .add
@@ -911,32 +911,36 @@
 add(t);%0A        
+    
 %7D%0A        int ga
@@ -937,72 +937,78 @@
     
-int gap = Math.max(Bu.get(0).min - min, max - Bu.get(N - 2).max)
+%7D%0A        Bu%5BN - 1%5D = new Bucket(max);%0A%0A        int gap = 0, pre = min
 ;%0A  
@@ -1038,18 +1038,16 @@
  %3C N
- - 1
 ; i++)
+ %7B
 %0A   
@@ -1059,24 +1059,159 @@
     
-gap = Math.max()
+if (Bu%5Bi%5D != null) %7B%0A                gap = Math.max(gap, Bu%5Bi%5D.min - pre);%0A                pre = Bu%5Bi%5D.max;%0A            %7D%0A        %7D%0A        return gap;
 %0A   
@@ -1325,16 +1325,19 @@
 m = %7B 2,
+ 5,
  9999999

Update Maximum Gap