164. 最大间距

题目描述：

主要思路：

利用桶排序的思路，取最大最小值的差值/个数，答案一定是大于等于这个数的，每个块为一个桶，维护这个桶内的最大最小值。

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int n=nums.size();
        if(n<2)
            return 0;
        int minval = *min_element(nums.begin(),nums.end());
        int maxval = *max_element(nums.begin(),nums.end());
        int d=max(1,(maxval-minval)/(n-1));
        int bucketsize = (maxval-minval)/d+1;
        vector<pair<int,int>> bucket(bucketsize,{-1,1});
        for(int i=0;i<n;++i)
        {
            int idx=(nums[i]-minval)/d;
            if(bucket[idx].first==-1)
                bucket[idx].first=bucket[idx].second=nums[i];
            else
            {
                bucket[idx].first=min(bucket[idx].first,nums[i]);
                bucket[idx].second = max(bucket[idx].second,nums[i]);
            }
        }
        int ans=0,la=-1;
        for(int i=0;i<bucketsize;++i)
        {
            if(bucket[i].first==-1)
                continue;
            if(la!=-1)
                ans=max(ans,bucket[i].first-bucket[la].second);
            la=i;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34