164. Maximum Gap

• 方法1：bucket sort
• • Complexity
  • 易錯點
• 方法2: radix sort

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.

方法1：bucket sort

思路：

官方題解： https://leetcode.com/problems/maximum-gap/solution/

triplebee：https://blog.csdn.net/accepthjp/article/details/54098370

要求用O(n)的排序應該直接想到bucket sort，官解給了計算和證明過程。首先要想到，所求的最大gap的最小值隻能是t = (max - min)/(n - 1)，也就是uniform gap時。那麼如果把桶的容量設為ceiling(t)，就確定了最大gap不會在桶内出現，必須是在兩個鄰居桶内。那麼一共會有多少個桶呢, 舉個例子：[1, 10, 20，50, 80, 100], t = ceiling((100 - 1)/(6 - 1) ) = 20, bucket_num = ceiling((max - min)/t)，也就是最多(max - min) / t + 1。或者這樣想：t這個值是我們将range均勻切割成n-1得來的，并且還ceiling了一下。那麼n - 1個 t 合起來肯定足以cover 整個range。當桶裝好之後，最大gap一定是前一個桶的最大值和下一個非空桶的最小值之間出現，是以對于所有桶，隻需要keep min and max。最後再掃過一遍所有buckets找到這個數就隻需要O(n)的時間。

需要的資料結構：

1. vector<int> bucketMin (n, INT_MAX)
2. vector<int> bucketMax (n, INT_MIN)

順便複習一下bucket sort，桶的數量都設為n。CLRS:

Complexity

Time complexity: O(n)

Space complexity: O(n)

易錯點

1. t 的計算公式：int t = ceil((mx - mn) / double (n - 1)); // 這裡是關鍵公式，double 和 ceil都很重要，不double沒有ceil的必要，不ceil後面recover會算錯
2. 最後掃桶的時候從i = 1開始掃，設定好初始值
3. 跳過所有空桶，potentially裝的時候就記錄一個set，記錄哪個桶非空

參考：https://leetcode.com/problems/maximum-gap/discuss/50698/C%2B%2B-solution-using-bucket-to-record

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        if (nums.empty()) return 0;
        int mx = *max_element(nums.begin(), nums.end());
        int mn = *min_element(nums.begin(), nums.end());
        int range = mx - mn;
        // edge case, [10], expected 0
        if (!range) return 0;
        
        // 建桶
        int n = nums.size();
        int t = ceil((mx - mn) / double (n - 1)); // 這裡是關鍵公式，double 和 ceil都很重要，不double沒有ceil的必要，不ceil後面recover會算錯
        vector<int> bucketMin(n, INT_MAX);
        vector<int> bucketMax(n, INT_MIN);
        
        // 裝桶
        for (int num: nums){
        	// idx算出num應該放哪個桶
            int idx = (num - mn) / t;
            bucketMin[idx] = min(bucketMin[idx], num);
            bucketMax[idx] = max(bucketMax[idx], num);
        }
        
        // 掃桶
        int result = t; // 最小不會小于t
        int prevMax = bucketMax[0]; //第一個桶包含最小值，是以一定不為空
        int nextMin = 0;
        for (int i = 1; i < n; i++){
            if (bucketMin[i] == INT_MAX) continue;
            nextMin = bucketMin[i];
            result = max(result, nextMin - prevMax);
            prevMax = bucketMax[i];
        }
        
        return result;
    }
};
           

方法2: radix sort

官方題解