Clear Python Solution


  • 1
    class Solution(object):
        def nextGreaterElement(self, n):
            """
            :type n: int
            :rtype: int
            """
            num = str(n)
            for i in range(len(num)-2, -1, -1):
                if num[i] < num[i+1]:
                    t = list(num[i:])
                    for j in range(len(t)-1, 0, -1):
                        if t[j]>t[0]:
                            first = t.pop(j)
                            rest = sorted(t)
                            res = int(num[:i] + first + ''.join(rest)) 
                            return res if res <= (2**31-1) else -1 
                    #print t
                    #raise ValueError('Error: cannot find bigger value!')
            return -1
    

  • 0
    A

    Great solution, thank you!


  • 1
    L

    @szhu3210 Could change the inner if statement to this. It will be faster and would change the solution from O(nlogn) to O(n)

                 if t[j]>t[0]:
                            t[0],t[j]=t[j],t[0]
                            t[1:]=reversed(t[1:])
                            res = int(num[:i] + ''.join(t)) 
                            return res if res <= (2**31-1) else -1
    
    #or even faster:
                            x,y=1,len(t)-1
                            while x<y:
                                t[x],t[y]=t[y],t[x]
                                x+=1
                                y-=1

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.