Python simple two pointers O(n)


  • 0
    A

    First, move right pointer to find first decrease index. Second, move left pointer to find another index just larger than right index. Third, swap them and reverse other previous number to generate the smallest larger number than original one.

    class Solution(object):
        def nextGreaterElement(self, n):
            """
            :type n: int
            :rtype: int
            """
            
            nums = [int(i) for i in list(str(n))][::-1]
            if len(nums)<2: return -1
        
            l= 0
            r= 1
            while r<len(nums):
                if nums[r]>=nums[r-1]:
                    r+=1
                elif nums[r]>=nums[l]:
                    l+=1
                else:
                    nums[l],nums[r]=nums[r],nums[l]
                    nums[:r] = nums[:r][::-1]
                    break
    
            res = int("".join([str(i) for i in nums[::-1]]))
            return  res if res<2**31 and res!=n else -1
    
    

Log in to reply
 

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