力扣 leetcode 164. 最大间距

因为需要用线性的时间复杂度和空间复杂度，所以想到用桶排序。（桶的规则是一个把所有数值分成n个区间，然后把所有是该区间内的值放入该区间中），由于相差的最大值必定大于等于（max-min）/nums.size（），所以把所有值分成这么多的桶，然后记录其中的最大值和最小值，相差的最大值必定为其中的某个桶中的最小值减去上一个桶的最大值

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int len=nums.size();
        if(len<=1){
            return 0;
        }
        int maxN=*max_element(nums.begin(),nums.end());
        int minN=*min_element(nums.begin(),nums.end());
        int distance=max(1,(maxN-minN)/(len-1));
        int counts=(maxN-minN)/distance+1;
        vector<pair<int,int>>bucket(counts,{-1,-1});//把所有的数字分成counts个桶
        for(int i=0;i<len;i++){
            int index=(nums[i]-minN)/distance;//根据nums[i]的值确定其在第index个桶
            if(bucket[index].first==-1){//-1说明是这个桶里的第一个值，所以把最小值和最大值都设置为该值
                bucket[index].first=bucket[index].second=nums[i];
            }
            else{
                if(bucket[index].first>nums[i]){//如果不是该桶的第一个值，则比较，如果比最小值小则把该桶最小值设置为它，如果是最大值则把最大值设置为它
                    bucket[index].first=nums[i];
                }
                else if(bucket[index].second<nums[i]){
                    bucket[index].second=nums[i];
                }
            }
        }
        int res=0;
        int last=0;//如果该桶内没有值，则跳过，通过last记录
        for(int i=1;i<counts;i++){
            if(bucket[i].first==-1){
                continue;
            }
            if(res<bucket[i].first - bucket[last].second){
                res=bucket[i].first - bucket[last].second;
            }
            last=i;
        }
        return res;
    }
};