C++ Solution. O(n)


#1
int Solution::perfectPeak(vector<int> &A) {
    int n = A.size();
    vector<int> greatest(n);
    vector<int> smallest(n);
    greatest[0] = A[0];
    for(int i = 1; i<A.size(); i++)
        greatest[i] = max(greatest[i-1], A[i]);
    smallest[n-1] = A[n-1];
    for(int i = A.size()-2; i>=0; i--)
        smallest[i] = min(smallest[i+1], A[i]);
    for(int i = 1; i<A.size()-1; i++){
        if(A[i]>greatest[i-1] && A[i]<smallest[i+1])
            return 1;
    }
    return 0;
}