LeetCode-164. Maximum Gap

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.      

题解：

最初没想到桶排序算法，只能Onlogn完成，看了讨论区，学习了桶排序，很高效的排序算法，但是对于海量数据并不适用，空间复杂度太高。

class Solution {
public:
    int bucketSort(vector<int>& nums, int n) {
        int maxi = nums[0], mini = nums[0];
        for (int i = 1; i < n; i++) {
            maxi = max(maxi, nums[i]);
            mini = min(mini, nums[i]);
        }
        int gap = max((maxi - mini)/(n - 1), 1);
        int m = (maxi - mini) / gap + 1;
        vector<int> bucketMax(m, INT_MIN);
        vector<int> bucketMin(m, INT_MAX);
        for (int i = 0; i < n; i++) {
            int k = (nums[i] - mini) / gap;
            if (nums[i] < bucketMin[k]) {
                bucketMin[k] = nums[i];
            }
            if (nums[i] > bucketMax[k]) {
                bucketMax[k] = nums[i];
            }
        }
        gap = bucketMax[0] - bucketMin[0];
        int i = 0;
        while (i < m) {
            int j = i + 1;
            while (j < m && bucketMax[j] == INT_MIN && bucketMin[j] == INT_MAX) {
                j++;
            }
            if (j == m) {
                break;
            }
            gap = max(gap, bucketMin[j] - bucketMax[i]);
            i = j;
        }
        return gap;
    }
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) {
            return 0;
        }
        return bucketSort(nums, n);
    }
};