164. Maximum Gap

https://leetcode.com/problems/maximum-gap/

Solution:
Do not have any clue with O(n) for this problem until searching online... (the reference is listed at bottom).
Will use Bucket Sort (https://en.wikipedia.org/wiki/Bucket_sort). Here are the some key points:
1: the bucket size is equivalent to the average distance between elements; then the maximum gap must be between the adjacent non-empty buckets;
2: the first bucket and the last bucket must not be empty.

Code:

class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int l = nums.size();
        if(l<2) return 0;
        int mx = INT_MIN, mn = INT_MAX;
        for(auto i:nums){
            mx = max(mx, i);
            mn = min(mn, i);
        }
        int bucket_size = (mx-mn)/l + 1;// average distance between elements.
        int bucket_num = (mx-mn)/bucket_size + 1;
        vector<int> bucket_mins(bucket_num, INT_MAX);
        vector<int> bucket_maxs(bucket_num, INT_MIN);
        for(auto i:nums){
            int index = (i-mn)/bucket_size;
            bucket_mins[index] = min(bucket_mins[index], i);
            bucket_maxs[index] = max(bucket_maxs[index], i);
        }
        int res = 0, ind_min = 1, ind_max = 0;//first bucket is not empty;
        while(ind_min<bucket_num){
            while(bucket_mins[ind_min] == INT_MAX ) ++ind_min; //last bucket is not empty;
            res = max(res, bucket_mins[ind_min]-bucket_maxs[ind_max]);
            ind_max = ind_min++;
        }
        return res;
    }
};

http://www.cnblogs.com/grandyang/p/4234970.html