164

class Solution {

struct bucket{
    int maxVal=INT_MIN, minVal=INT_MAX;
    bool used=false;
};

public:
    int maximumGap(vector<int>& nums) {
        if(nums.empty() || nums.size()<2)
            return 0;
        int mine = *min_element(nums.begin(), nums.end());
        int maxe = *max_element(nums.begin(), nums.end());
        int bucketSize = max(1, (maxe-mine)/int(nums.size()-1));
        int bucketNum = (maxe-mine)/bucketSize+1;

        vector<bucket> buckets(bucketNum);

        for(auto num: nums){
            int idx = (num-mine)/bucketSize;
            buckets[idx].used = true;
            buckets[idx].minVal = min(num, buckets[idx].minVal);
            buckets[idx].maxVal = max(num, buckets[idx].maxVal);
        }

        int prevMax = mine, ans = 0;
        for(auto bucket: buckets){
            if(!bucket.used)
                continue;
            ans = max(ans, bucket.minVal-prevMax);
            prevMax = bucket.maxVal;
        }
        return ans;
    }
};