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(currenttmp>gap) gap=currenttmp;
current=tmp;
}
return gap;
}
Use a heap to solve


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?