C++ 9ms solution


  • 0
    P

    divide the whole interval into chunks, each with length (max - min - 1)/(n-1) +1;
    The maximum gap will not appears in the same chunk. We first put all the numbers into its responding chunks and go through chunk array to find the maximum gap:

    typedef long long LL;
    typedef pair<LL,LL> pLL;
    typedef pair<int,int> ii;
    
    class Solution {
    public:
        int maximumGap(vector<int>& nums) {
            int n = nums.size();
            if(n<2) return 0;
            int m = nums[0], M = nums[0];
            for(auto k:nums){
                m = min(m,k);
                M = max(M,k);
            }
            if(M==m) return 0;
            int L = (M-m-1)/(n-1)+1;
            vector<ii> chuck(n,ii(-1,-1));
            for(auto k:nums){
                int j = (k-m)/L;
                if(chuck[j].first == -1){
                    chuck[j].first = chuck[j].second = k;
                }
                else{
                    chuck[j].first = min(chuck[j].first,k);
                    chuck[j].second = max(chuck[j].second,k);
                }
            }
            int ans = L, tmp = chuck[0].second;
            for(int i=1;i<n;++i){
                if(chuck[i].first!=-1){
                    ans = max(chuck[i].first - tmp, ans);
                    tmp = chuck[i].second;
                }
            }
            return ans;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.