Maximum Gap

题目来源
Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Try to solve it in linear time/space.
Return 0 if the array contains less than 2 elements.
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

给一个未排序的数组，找出这些元素排好序之后两两元素的最大差。
假如不是需要用线性时间、空间，那直接排好序遍历一遍就知道了，代码如下：

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        int r = 0;
        sort(nums.begin(), nums.end());
        for (int i=1; i<n; i++) {
            r = max(r, nums[i] - nums[i-1]);
        }
        return r;
    }
};

但是线性时间空间的话怎么办呢！提到了线性空间，感觉应该要用上，空间换时间嘛，好好想想！
实在是想不出来了…感觉脑细胞不够用了！
桶排序！可怕，完全想不到用这个，就是那个大家熟知的鸽笼原理。先找到最小值和最大值，然后把max-min划分为n-1块，把除了最大值和最小值的n-2个元素放入n-1个桶中，然后肯定有一个桶是没数字的，然后记录所有桶内部的最大值和最小值，然后遍历一遍，只需计算该桶的最小值和上一个桶的最大值以及该桶的最大值和下一个桶的最小值之间的差，记录比较即可得出结果，代码如下：

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1)
            return 0;
        int minN = nums[0], maxN = nums[0];
        for (int i=1; i<n; i++) {
            minN = min(minN, nums[i]);
            maxN = max(maxN, nums[i]);
        }
        double gap = double(maxN - minN) / double(n - 1);
        vector<int> minG(n-1, INT_MAX);
        vector<int> maxG(n-1, INT_MIN);
        for (int i=0; i<n; i++) {
            if (nums[i] != minN && nums[i] != maxN) {
                int idx = (nums[i] - minN) / gap;
                minG[idx] = min(minG[idx], nums[i]);
                maxG[idx] = max(maxG[idx], nums[i]);
            }
        }
        int r = 0;
        int pre = minN;
        for (int i=0; i<n-1; i++) {
            if (minG[i] != INT_MAX) {
                r = max(r, minG[i] - pre);
                pre = maxG[i];
            }
        }
        r = max(r, maxN - pre);
        return r;
    }
};