Maximum Gap 400

Question

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.

Challenge

Sort is easy but will cost O(nlogn) time. Try to solve it in linear time and space.

Solution

这道题如果直接用普通排序，则可以轻易求解，但是复杂度是O(nlogn)。题目要求O(n)则考虑线性时间排序。这里用桶排序Bucket Sort。桶排序步骤如下：

1. 首先找出数组的最大值和最小值，特殊情况是最大值和最小值相等则说明所有值相等，直接返回0即可

2. 然后要确定每个桶的容量，即为(最大值 - 最小值) / 个数 + 1，

3. 再确定桶的个数，即为(最大值 - 最小值) / 桶的容量 + 1

4. 遍历整个数组，根据index = (nums - min) / bucketSize将每个数加入不同的桶中，这里用两个array来记录这个桶里的最大值和最小值（因为只保留着两个值就足够了，不用记录其他的数）。用一个set来记录每个桶是否被放过数。如果该桶内没有被放过数，则直接将该桶的最大值和最小值设为当前数，否则需要和最值进行比较后更新最值。

5. 相邻的两个数有两种情况：1）落在同一个桶里 2）小的那个是前一个桶的最大值大的那个是后一个痛的最小值。落在不同桶里的数之间的间距一定比落在相同桶里的数之间的间距大，因此最大间距的两个数不会在同一个桶中，而是后一个桶的最小值和前一个桶的最大值之间的间距，因此遍历两个array，用后一个桶的最大值减去前一个桶的最小值，记录最大差值即可

代码如下：

class Solution {
    /**
     * @param nums: an array of integers
     * @return: the maximum difference
     */
    public int maximumGap(int[] nums) {
        // write your code here
        if(nums == null || nums.length < 2){
            return 0;
        }

        // sort version
        // Arrays.sort(nums);

        // int diff = 0;
        // for(int i = 1; i < nums.length; i++){
        //     diff = Math.max(diff, nums[i] - nums[i - 1]);
        // }

        // return diff;

        //Bucket sort
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int n = nums.length;
        for(int num : nums){
            max = Math.max(max, num);
            min = Math.min(min, num);
        }

        if(max == min){
            return 0;
        }

        int bucketSize = (max - min) / n + 1;
        int bucketNum = (max - min) / bucketSize + 1;
        int[] bucketMin = new int[bucketNum];
        int[] bucketMax = new int[bucketNum];
        HashSet<Integer> set = new HashSet<Integer>();
        for(int num : nums){
            int index = (num - min) / bucketSize;
            if(!set.contains(index)){
                bucketMin[index] = num;
                bucketMax[index] = num;
                set.add(index);
                continue;
            }

            if(bucketMin[index] > num){
                bucketMin[index] = num;
            }
            if(bucketMax[index] < num){
                bucketMax[index] = num;
            }
        }

        //一定会有数落在0bucket里，因为index = (num - min) / bucketSize，当num = min时就落在0桶里，所以第一个非空的桶一定为0
        int pre = 0;
        int res = 0;
        //寻找下一个非空的桶，空的桶就跳过
        for(int i = 1; i < bucketNum; i++){
            if(!set.contains(i)){
                continue;
            }
            res = Math.max(res, bucketMin[i] - bucketMax[pre]);
            pre = i;
        }

        return res;
    }
}