Python O(n) solution in simple way


#1
class Solution:
    # @param A : list of integers
    # @return an integer
    def perfectPeak(self, A):
        abs_maxi = A[0]
        so_far_maxi = A[0]
        ans = 0
        n = len(A)
        for i in range(1,n):
            if A[i] > so_far_maxi:
                so_far_maxi = A[i]
            if A[i] > abs_maxi:
                if ans == 0:
                    abs_maxi = so_far_maxi
                ans = 1
            if A[i] < abs_maxi:
                ans = 0
                abs_maxi = so_far_maxi
        if abs_maxi == A[n-1]:
            return 0
        return ans   

#2

Both O(n) time and O(1) space. Great thinking.