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.

hint:

　　Bucket Sort

 1 public class MaxGap {
 2     public int maximumGap(int[] nums) {
 3         if (nums == null || nums.length < 2)
 4             return 0;
 5         int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
 6         for (int i = 0; i < nums.length; i++) {
 7             if (max < nums[i]) max = nums[i];
 8             if (min > nums[i]) min = nums[i];
 9         }
10         int bucket = (max - min) / nums.length + 1; // the bucket size is at least 1
11         int n = (max - min) / bucket + 1;
12         int[] mins = new int[n];
13         int[] maxs = new int[n];
14         for (int i = 0; i < n; i++) {
15             mins[i] = Integer.MAX_VALUE;
16             maxs[i] = Integer.MIN_VALUE;
17         }
18         for (int i = 0; i < nums.length; i++) {
19             int k = (nums[i] - min) / bucket;
20             if (mins[k] > nums[i]) mins[k] = nums[i];
21             if (maxs[k] < nums[i]) maxs[k] = nums[i];
22         }
23         int maxGap = 0, pre = 0;
24         for (int i = 1; i < n; i++) {
25             if (mins[i] <= max) {
26                 if (maxGap < mins[i] - maxs[pre]) {
27                     maxGap = mins[i] - maxs[pre];
28                 }
29                 pre = i;
30             }
31         }
32         return maxGap;
33     }
34     public static void main(String[] args) {
35         int[] nums = {1, 1000};
36         MaxGap mg = new MaxGap();
37         System.out.println(mg.maximumGap(nums));
38     }
39 }