556. Next Greater Element III.md

556. Next Greater Element III

https://leetcode.com/problems/next-greater-element-iii/

Given a positive integer n, find the smallest integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive integer exists, return -1.

Note that the returned integer should fit in 32-bit integer, if there is a valid answer but it does not fit in 32-bit integer, return -1.

Example 1:

Input: n = 12
Output: 21

Example 2:

Input: n = 21
Output: -1

Constraints:

• 1 <= n <= 231 - 1

代码

• Same idea, refer to 31. Next Permutation

class Solution(object):
    def nextGreaterElement(self, N):
        """
        :type n: int
        :rtype: int
        """
        return nextGreaterElement(N)

def nextGreaterElement(N):
    A = list(map(int, list(str(N))))
    n = len(A)
    i = n - 1
    while i > 0 and A[i-1] >= A[i]:
        i -= 1
    if i == 0:
        # digits in descending order, like "4321", return -1.
        return -1

    if i > 0:
        j = i + 1
        while j < n and A[j] > A[i-1]:
            j += 1
        # swap
        A[i - 1], A[j - 1] = A[j - 1], A[i - 1]
    A[i:] = A[i:][::-1]
    res = int("".join(list(map(str, A))))
    return res if res <= ((1<<31)-1) else -1