Python Solution with 39ms


  • 0
    R

    The step of solution:

    1. convert the number to the reverse int array: that means the minimum index of array is the Least Significant Octet
      e.g. 1234 ->[4,3,2,1]

    2. Search the array from the index 0, compare it with the next index Octet .
      if all the octets keep increase trend, then return -1
      e.g. 9631->[1,3,6,9]-> 1<3<6<9 then return -1

    3. if not, find the octet index i which not keep the trend. then revert the octets from the index 0 to the i-1 to find the next greater number.
      83541->[1,4,5,3,8]->1<4<5>3 -> 83145, find the octet 3 and index 3, revert 541->145

    4. find the next largest number (index j) and swap them.
      e.g. 3541, the next largest number than 3 is 4, swap 3 with 4. 83145->84135

    5. covert the array to number

    6. if the number is more than positive 32 bit number, return -1, or return the number

    
    class Solution(object):
    
        max_int = 2147483648
        def nextGreaterElement(self, n):
            nums = self.convert2array(n)
            for i in range(1,len(nums)):
                if nums[i] < nums[i-1]:
                    nums = self.reverse(nums,i)
                    for j in range(i - 1, -1, -1):
                        if nums[j] > nums[i]:
                            nums = self.swap(nums, j, i)
                            break
                    m = self.convert2num(nums)
                    return -1 if m > self.max_int else m
            return -1
    
        def convert2array(self,n):
            nums = []
            while n> 0:
                nums.append(n%10)
                n //= 10
            return nums
    
        def convert2num(self,nums):
            m = 0
            for j in range(len(nums) - 1, -1, -1):
                m = m * 10 + nums[j]
            return m
    
        def reverse(self, nums,end):
            i = 0
            j = end - 1;
            while i < j:
                nums = self.swap(nums,i,j)
                i += 1
                j -= 1
            return nums
    
        def swap(self,nums,i,j):
            t = nums[j]
            nums[j] = nums[i]
            nums[i] = t
            return nums
    

Log in to reply
 

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