"""
给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。

注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。

 

示例 1：

输入：n = 12
输出：21
示例 2：

输入：n = 21
输出：-1
 

提示：

1 <= n <= 231 - 1
通过次数9,006提交次数28,809

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-greater-element-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""

#先从右到左找到i-1比i小的第一个位置，然后再在i-1的右边找比i-1这一位大的最小的数，同i-1交换，最后对i:-1排序

class Solution:
    def nextGreaterElement(self, n: int) -> int:
        digits = []
        while n > 0:
            bit, n = n % 10, n // 10
            digits.insert(0, bit)

        for i in range(len(digits) - 1, -1, -1):
            if i > 0 and digits[i] > digits[i - 1]:
                break
        if i == 0:
            return -1

        j = i
        for k in range(i, len(digits)):
            if digits[i - 1] < digits[k] < digits[j]:
                j = k
        tmp = digits[i - 1]
        digits[i - 1] = digits[j]
        digits[j] = tmp
        digits = digits[:i] + sorted(digits[i:])

        rtn = 0
        for each in digits:
            rtn = rtn * 10 + each
        if rtn > 2 ** 31 - 1:
            return -1
        return rtn
