首页 > 代码库 > [leetcode]Maximum Gap

[leetcode]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.


代码:

int maximumGap(vector<int> &num) {  //C++
        if( num.size() <2) 
            return 0;
       
        map<int,int> myMap;
        for(int i=0; i<num.size(); i++)
            myMap.insert(make_pair(num[i],i));
        
        int pos =1,max=0,dif,temp;    
        map<int,int>::iterator iter=myMap.begin();
        temp = iter->first;
        iter++;
        for(; iter!=myMap.end(); iter++)
        {
            dif = abs(iter->first-temp);
            if(dif >max)
                max = dif;
            temp = iter->first;
            
        }
        return max;
    }


[leetcode]Maximum Gap