Use a heap to solve


  • -9
    G
    int maximumGap(vector<int> &num) 
    	{
    		if(num.size()<2) return 0;
    
    		int gap=INT_MIN;
    		
    		priority_queue<int> buffer;
    		for(int i=0;i<num.size();i++)
    		{
    			buffer.push(num[i]);
    		}
    
    		int current=buffer.top();
    		buffer.pop();
    
    		for(int i=0;i<num.size()-1;i++)
    		{
    			int tmp=buffer.top();
    			buffer.pop();
    			if(current-tmp>gap) gap=current-tmp;
    			current=tmp;
    		}
    
    		return gap;
        }

  • 1
    D

    Hi!
    Your solution is similar to the following: run heap sort and then look through the sorted array and find max gap (check two consecutive elements). But the complexity of this algorithm will be O (n * log(n)), where n = num.size()), and thats because the cost of pop() and push() is O(log(n)). But how about the O(n) solution?


Log in to reply
 

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