164. Maximum Gap

problem description

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.

Note:

• You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

• Try to solve it in linear time/space.

algorithm thought

乍一看发现只要排好序，然后得到两两直接差值的最大值就行了。问题是这里要求我们使用线性时间解决问题，使用普通的比较排序，最快的就是快排，时间复杂度是O(lgn)。使用比较排序是不行的，这里需要使用线性时间排序算法，桶排序就很适合这里。桶排序原理是将数据按组分入桶中，对于桶里的数在进行线性时间排序。但是对于这题，巧妙的处理可以省去桶里数据排序这一步。

桶的大小是关键，这里我们首先遍历一遍数组，得到数组的最大值和最小值。最大值减去最小值就可以得到最大的gap。然后除以size-1，就能得到平均的gap。也就是这个题的可能的最小值。我们令这个值为桶的大小。桶里的数字直接的差值我们是不需要记录的，只需要记录桶直接的数字差值。

然后就是遍历数组，将数字放入桶内，保存桶的最大最小值。最后再遍历一次桶，得到最后的max_gap

code

class Solution {
public:    
    int maximumGap(vector<int>& nums) {
        if(nums.size()<=1)
            return 0;
        int  ma=INT_MIN,mi=INT_MAX;
        for(auto num:nums){
            ma=max(num,ma);
            mi=min(num,mi);
        }
        int min_gap=(ma-mi)/(nums.size()-1);
        min_gap=max(min_gap,1);
        int bucket_number=(ma-mi)/min_gap;
        vector<pair<int,int>> bucket(bucket_number+1,make_pair(INT_MAX,INT_MIN)); //需要多一个bucket装最大的那个数字
        for(auto num:nums){
            int index=(num-mi)/min_gap;
            bucket[index].first=min(bucket[index].first,num);
            bucket[index].second=max(bucket[index].second,num);
        }
        int i=0,res=INT_MIN;
        while(i<bucket.size()){
            int j=i+1;
            while(j<bucket.size()&&bucket[j].first==INT_MAX){
                j++;
            }
            if(j==bucket.size())
                break;
            res=max(res,bucket[j].first-bucket[i].second);
            i=j;
        }
        return res==INT_MIN?0:res;
    }
};

algorithm analysis

桶排序只需要线性时间，时间复杂度O(n)，空间复杂度O(n).