题目描述

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

样例

给定数组 nums = [5,9,8,3,15] 排序后为：[3,5,8,9,15] 相邻元素之差最大的是15-9=6，返回6.

要求线性时间

算法

(桶排序) $O(n)$

首先肯定要排序
然而基于比较的算法的bound都是$O(n*long(n))$
因此采用基于计数的排序算法
实际采用桶排序，熟悉计数排序的话计数排序为桶大小为1的桶排序
例如值为1-1000的数需要排序，一共有nums.size个。那么桶间隔为100的话，共有10个桶。
如下
桶1： 1-100
桶2： 101-200
…

因为所求值是连续两个数的最大值。
所以实际上我们不需要采用计数排序将他排好。
我们只需要维护每个桶的最大值和最小值。

那么所求值就是当前桶的最小值（如果有的话）减去上一个有值得桶的最大值。
有一些桶可能是空的。

如果桶间隔太大，那么有可能最大值和最小值落在同一个桶，如果桶间隔太小，那么效率太低。
我们想让桶间隔尽可能的大，可以认为桶间隔是最小计量单位。
数组中最大值为MAX,最小值为MIN。
那么桶间隔最大为$len = (MAX-MIN)/(nums.size()-1)$ 只有当所有数均匀分布时才会有这种情况。

C++ 代码：

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        if (nums.size()<2) return 0;
        int N = nums.size();
        int MaxNum = INT_MIN;
        int MinNum = INT_MAX;
        for (int i = 0;i<nums.size();++i){
            MaxNum = max(nums[i],MaxNum);
            MinNum = min(nums[i],MinNum);
        }
        if (MaxNum == MinNum) return 0;
        double len = (MaxNum-MinNum)*1.0/(N-1);

        int BucketSize = floor((MaxNum-MinNum)/len)+1;


        vector<int> minbucket(BucketSize,INT_MAX);
        vector<int> maxbucket(BucketSize,INT_MIN);



        for (int i = 0;i<nums.size();++i){
            int index = floor((nums[i]-MinNum)/len);
            minbucket[index] = min(minbucket[index],nums[i]);
            maxbucket[index] = max(maxbucket[index],nums[i]);
        }

        int delta = 0;
        int premax = maxbucket[0];
        for (int i = 1;i<BucketSize;++i){
            int curdelta = 0;
            if (minbucket[i]!=INT_MAX){
                delta = max(minbucket[i] - premax,delta);
                premax  = maxbucket[i];
            }

        }
        return delta;


    }
};