164 Maximum Gap

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.

class Solution {
public:
    int maximumGap(vector<int> &num) {
        int n = num.size();
        if (n<=1)
            return 0;
        int maxVal = num[0],minVal = num[0];
        for (int i=1;i<n;i++)
        {
            maxVal = max(maxVal,num[i]);
            minVal = min(minVal,num[i]);
        }
        
        int step = (maxVal-minVal)/(n)+1;
        int numberBucket = (maxVal-minVal)/step+1;
        vector<int> minVec = vector<int>(numberBucket,INT_MAX);
        vector<int> maxVec = vector<int>(numberBucket,INT_MIN);
        for (int i=0;i<n;i++)
        {
            int index = (num[i]-minVal)/step;
            minVec[index] = min(minVec[index],num[i]);
            maxVec[index] = max(maxVec[index],num[i]);
        }
        int res = 0;
        int last = 0;
        for (int i=0;i<numberBucket;i++)
        {
            if (minVec[i]==INT_MAX && maxVec[i]==INT_MIN)
                continue;
            res = max(maxVec[i]-minVec[i],res);
            if (i>0)
                res = max(res,minVec[i]-maxVec[last]);
            last = i;
        }
        return res;
            
    }
};