Leetcode-164-Maximum Gap

给定一个未排序的数组，求排序后数组中相邻元素之差的最大值。

这题最大的思维盲点就在于的复杂度让人直接放弃包含排序的算法，但实际上排序算法有很多，比较排序的下界才是，我们还是可以考虑非比较排序的，比如这道题用到的桶排序。

桶排序工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来即得到有序序列。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间。

这道题只考虑相邻元素之差的最大值，我们可以对桶排序稍作改动得到本题的解法。具体说来，我们的思路分两步，第一步是分桶，假设题目给定无序数组的个元素都位于中，则相邻元素之差最大值必然不小于,因此我们可以把，作为桶的大小（若等于0则取1，以使得桶有意义），这样分到同个桶中的元素之差我们就可以不考虑了，最终的结果一定是某个桶中的最大元素和另一个桶中的最小元素（这样两者才相邻）之差。于是分桶步骤进行完以后我们已经做了非常有效的剪枝。第二步就是记录每个桶中的最大元素和最小元素，并考察前一个桶的最大元素和后一个桶的最小元素之差，遍历所有桶并取最大差值即得到最终的解。

具体算法实现如下：

https://leetcode.com/problems/maximum-gap/discuss/50694/12ms-C%2B%2B-Suggested-Solution

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return 0;
        auto lu = minmax_element(nums.begin(), nums.end());
        int l = *lu.first, u = *lu.second;
        int gap = max((u - l) / (n - 1), 1);
        int m = (u - l) / gap + 1;
        vector<int> bucketsMin(m, INT_MAX);
        vector<int> bucketsMax(m, INT_MIN);
        for (int num : nums) {
            int k = (num - l) / gap;
            if (num < bucketsMin[k]) bucketsMin[k] = num;
            if (num > bucketsMax[k]) bucketsMax[k] = num;
        }
        int i = 0, j; 
        gap = bucketsMax[0] - bucketsMin[0];
        while (i < m) {
            j = i + 1;
            while (j < m && bucketsMin[j] == INT_MAX && bucketsMax[j] == INT_MIN)
                j++;
            if (j == m) break;
            gap = max(gap, bucketsMin[j] - bucketsMax[i]);
            i = j;
        }
        return gap;
    }
};