164. Maximum Gap (1)

Link

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.

Example 1:

Input: [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either
             (3,6) or (6,9) has the maximum difference 3.

Example 2:

Input: [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.

Note:

• You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

• Try to solve it in linear time/space.

Solution

思路是將所有元素放到籃子裡:

我们把 0 3 4 6 23 28 29 33 38 依次装到三个箱子中
    0            1            2           3
 -------      -------      -------     ------- 
|  3 4  |    |       |    | 29    |   | 33    |
|   6   |    |       |    |  23   |   |       |
|  0    |    |       |    |  28   |   |  38   |
 -------      -------      -------     ------- 
  0 - 9       10 - 19      20 - 29     30 - 39
我们把每个箱子的最大值和最小值表示出来
 min  max     min  max     min  max  min  max 
 0     6      -     -      23   29   33   38

然後我們希望每個箱子的最小值-上個不為空的箱子內的最大值，可以是maxGap的所在。 ex: 箱子2的min - 箱子0的max = 23-6 = 17即是maxGap。

但這會需要在同個箱子裡的元素差，不會是maxGap。所以要避免這件事情，我們必須審慎決定每個箱子的capacity。

已知目前元素間的average gap 應該是 MaxValue - MinValue/(n-1)，那麼maxGap必定會大於等於averageGap，若將籃子的容量設成averageGap，那麼就可以確保maxGap就只有可能發生在兩個籃子之間的gap。

所以可知bucket 的 capacity就是 Max-Min/(n-1)

class Solution {
    public int maximumGap(int[] nums) {
          int len = nums.length;
        if (len < 2) {
            return 0;
        }
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        //remember to cast (max-min)/(len-1) to double
        int capacity = (int) Math.ceil((double) (max - min) / (len - 1));

        if (capacity == 0) //all the same
            return 0;


        int[] bucketMax = new int[len - 1];
        int[] bucketMin = new int[len - 1];
        //Remember to fill the default value of buckets
        Arrays.fill(bucketMax, Integer.MIN_VALUE);
        Arrays.fill(bucketMin, Integer.MAX_VALUE);
        for (int num : nums) {
            //Remember to skip max and min, since they need to be handled separately, they might can't fit into a buckets
            //ex. [1, 2, 1000] , max it 1000, cap = 1000-1/2 = 500, 1000-1/500 = 2, however we only have 2 buckets[0, 1]
            if (num == min || num == max) continue;
            int index = (num - min) / capacity; //remember to use this way to get index
            bucketMax[index] = Math.max(bucketMax[index], num);
            bucketMin[index] = Math.min(bucketMin[index], num);
        }
        int maxGap = 0;
        int preMax = min; //remember it shall be min at beginning
        for (int i = 0; i < len - 1; i++) {

            //remember to skip empty buckets
            if (bucketMax[i] == Integer.MIN_VALUE && bucketMin[i] == Integer.MAX_VALUE) {
                continue;
            }
            maxGap = Math.max(maxGap, bucketMin[i] - preMax);
            preMax = bucketMax[i];
        }
        //remember to handle max value case
        maxGap = Math.max(maxGap, max - preMax);
        return maxGap;
    }
}