775. Global and Local Inversions

Apparently, the local inversion is a special case of global inversion. If we can find a global inversion which is not local inversion, then the permutation is not ideal. In other words, we need to check whether there exists i and j where j - i > 1 and A[i] > A[j]. Traverse the array from left to right, record the max value, if max > A[i + 2] then the permutation is not ideal.

public boolean isIdealPermutation(int[] A) {
    int max = 0;
    for(int i = 0; i < A.length - 2; i++) {
        max = Math.max(A[i], max);
        if( A[i + 2] < max )
            return false;
    }
    return true;
}