Total Accepted: 26010 Total Submissions: 102064 Difficulty: Hard

 

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

/* n 个数，n-1个桶1,2,3,4,5,77-1/5=1.2;1,2.2)   2.2,3.4)  3.4,4.6)   4.6,5.8)  5.8,7  2        3          4          5        7         */class Solution {public:    int maximumGap(vector
        
         & nums) {        int nums_size = nums.size();        int nums_min = nums_size==0 ? 0 : *min_element(nums.begin(),nums.end());        int nums_max = nums_size==0 ? 0 : *max_element(nums.begin(),nums.end());        if(nums_size <= 2){            return nums_max-nums_min;        }        if(nums_max-nums_min<=1){            return nums_max-nums_min;        }        vector
         
           bucket_max(nums_size,INT_MIN);        vector
          
            bucket_min(nums_size,INT_MAX);            double bucket_gap = (nums_max-nums_min)*1.0/(nums_size-1);        for(int i=0;i
          
         
        

 

Next challenges: