164 - Maximum Gap

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.
Credits:
Special thanks to @porker2008 for adding this problem and creating all test cases.
Hide Tags
Sort

看起来题目很容易，排个序，然后算个差值就可以了，（可以通过测试不会超时）
但其实没那么简单，因位要求线性的时空复杂度。
线性排序的方法不多，计数排序（count）、基数排序（radix）、桶排序（bucket）
如果最大最小值之间的距离太大，计数排序就不合适了，如果个数太多，radix也会比较折腾，看起来桶排序会好一点。

进一步的分析：
其一，对于长度为 sz 的数组，它存放着 mini 到 maxi 之间的数字，可以看成就是把所有 mini maxi 的数字，分成了 sz 个组，
        只不过随机分布的情况是，有的组里有一个或者几个数字被选中，有的组里没有数字被选中。
其二，如果每个组都选一个数字，且数字之间距离相等，那么我们会得到一个均匀分布的间隔： （maxi - mini）/ sz，
        同一个组里，每个组的首尾数字的间隔，也就是（maxi - mini）/ sz 向下取整，
        如果数字之间的分布不均匀，相邻两个数的所有间隔中，那个最大的间隔，至少是上面的均匀间隔（不然就到不了 maxi 了）
        因此，对这个间隔（可能不是个整数）向上取整，就是 （maxi - mini）/ sz + 1 ，这就是最大间隔的最小值。
也就是说，这个题目所问的最大的间距，产生于组跟组之间，而不是组内。
（当然某些组之间的间隔可能很小，但一定有两个组，间隔大于等于（maxi - mini）/ sz + 1 ）

所以，现在要做的事情，是把这些数字，放入到均匀划分的某个组里，全部放完之后，去看组与组之间的间隔就可以了。
这实际上就是桶排序，桶的个数就是输入的数列里的数字的个数 sz ，桶的容量是 （maxi - mini）/ sz + 1  。
进一步的简化是：
既然我们关心的是桶和桶之间的距离，那么实际上就不必关注桶内的情况了，只需要维护每个桶里头的桶内最大最小值就可以了。

这道题并没有直接搞定最优解，也是去搜了别人的帖子讲解的，有些讲得比较清楚的：
不知道是不是大家都是看同一份原始的讲解，几乎所有的帖子都有这么一段：
        int len = (maxN - minN) / n + 1;
        int bucketNum = (maxN - minN) / len + 1;
号称是第一步计算出每个桶的长度，第二步再计算桶的个数，这两行把我还真看晕了好一阵：
如果你既不知道桶的个数，也不知道桶的长度，你还求个球。
你在计算桶的长度的时候，就已经默认了桶的个数是 n （当然实际上也就是 n ），
所以根本不用再用长度反过来算一次桶的个数，直接用 n 就好了。

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int rst=0;
        int sz=nums.size();
        if(sz>1)
        {
            int mini=INT_MAX, maxi=INT_MIN;                                    //获取最大最小值
            for(auto nn : nums)
                mini=min(nn, mini), maxi=max(nn, maxi);
           
            int bucketCapacity=(maxi-mini)/sz + 1;                             //每个桶的容量都是这么多
            vector<pair<int, int>> buckets(sz, make_pair(INT_MAX, INT_MIN));   //sz个桶，桶内只管最大最小值
            for(auto nn : nums)
            {
                int bucketId = (nn-mini)/bucketCapacity;                       //定位应该去哪个桶。
                buckets[bucketId].first = min(nn, buckets[bucketId].first);
                buckets[bucketId].second= max(nn, buckets[bucketId].second);
            }
           
            int lastmax=mini;                                                  //计算桶间距离，更新结果
            for(auto b : buckets)
                if(INT_MAX != b.first)
                    rst = max(rst, (b.first - lastmax)), lastmax = b.second;
        }
        return rst;
    }

    //。。。。。。sort函数本身是 nlgn 的复杂度，这个虽然能过，但并不满足要求。。。。。。
    int maximumGap_nlgn(vector<int>& nums) {
        int rst=0;
        int sz=nums.size();
        if(sz>1)
        {
            sort(nums.begin(), nums.end());
           
            for(int ii=1; ii<sz; ++ii)
            {
                int gap = nums[ii]-nums[ii-1];
                if(gap>rst)
                    rst = gap;
            }
        }
        return rst;
    }
};
8 ms.