maximum-gap.cpp

class Solution {
public:
    // https://leetcode.com/problems/maximum-gap/discuss/50643/bucket-sort-JAVA-solution-with-explanation-O(N)-time-and-space ?@hot13399????
    // Then the maximum gap will be no smaller than ceiling[(max - min ) / (N - 1)]. ???????????ceiling[(max - min ) / (N - 1)]????gap???????maximum gap?????????
    // https://leetcode.com/problems/maximum-gap/discuss/50694/12ms-C++-Suggested-Solution
    // https://www.cnblogs.com/grandyang/p/4234970.html
    /*
        1. ????max_gap???????????????????????max_gap???? gap=ceiling[(max - min ) / (N - 1)]
        2. gap????????????????????????gap?????gap?????max_gap?
        3. ????????????????????????????cnt
        4. ??????????????????????max_gap?????????????????????????????minv,maxv???????????????
        5. max_gap??? ??????????????? ???
        6. ?????????????????pre?? (?????????? ?????)
    */
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return 0;
        auto t = minmax_element(nums.begin(), nums.end());
        int l = *t.first;
        int r = *t.second;
        int gap=(r-l)/n+1;
        int cnt=(r-l)/gap+1;

        vector<int> minv(cnt,INT_MAX),maxv(cnt,INT_MIN);
        for(auto num:nums){
            int id=(num-l)/gap;
            minv[id]=min(minv[id],num);
            maxv[id]=max(maxv[id],num);
        }

        int res=0;
        int pre=0;
        for(int i=1;i<cnt;i++){
            if(maxv[i]==INT_MIN) continue;
            res=max(res,minv[i]-maxv[pre]); 
            pre=i;
        }
        
        return res;
    }
};