Simple solution in O(3N)


#1

int Solution::perfectPeak(vector &A) {
int n=A.size();
vectorv(n);
vectorr(n);
v[0]=A[0];
for(int i=1;i<n;i++){
v[i]=max(A[i],v[i-1]);
}
r[n-1]=A[n-1];
for(int i=n-2;i>=0;i–){
r[i]=min(r[i+1],A[i]);
}
for(int i=1;i<n-1;i++){
if(v[i]!=v[i-1] && r[i]!=r[i+1]){
return 1;
}
}
return 0;
}