Solution in O(n) using Python


#1
def getGth(A, st):
while len(st) > 0:
    if st[-1] > A:
        return st[-1]
        
    st.pop()

return -1

class Solution:
# @param A : list of integers
# @return a list of integers
    def nextGreater(self, A):
        st = []
        gts = []
        for i in range(len(A)-1,-1,-1):
            gts.append(getGth(A[i],st))
            st.append(A[i])
        
        return gts[::-1]