1.题目基本信息

1.1.题目描述

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

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

1.2.题目地址

https://leetcode.cn/problems/next-greater-element-iii/description/

2.解题方法

2.1.解题思路

等价于求「下一个排列」；同Leetcode 31. 下一个排列

2.2.解题步骤

第一步，从后往前找到第一个小于后面数字的数位i1和数值digit1（数位从0开始）

第二步，从后往前找到第一个大于digit1的数位i2和数字digit2

第三步，计算交换digit1和digit2位后的数

第四步，将后面i1位进行翻转

3.解题代码

python3代码

class Solution:
    def nextGreaterElement(self, n: int) -> int:
        # 思路：参考 Leetcode 31. 下一个排列
        # 第一步，从后往前找到第一个小于后面数字的数位i1和数值digit1（数位从0开始）
        i1 = 1
        n1 = n
        while n1 >= 10 and n1 % 10 <= (n1 // 10) % 10:
            i1 += 1
            n1 //= 10
        n1 //= 10
        digit1 = n1 % 10
        if n1 == 0:
            return -1
        # 第二步，从后往前找到第一个大于digit1的数位i2和数字digit2
        i2 = 0
        n2 = n
        while n2 % 10 <= digit1:
            i2 += 1
            n2 //= 10
        digit2 = n2 % 10
        # 第三步，计算交换digit1和digit2位后的数
        n = n - digit1 * (10 ** i1) - digit2 * (10 ** i2) + digit2 * (10 ** i1) + digit1 * (10 ** i2)
        # 第四步，将后面i1位进行翻转
        num = 0
        n3 = n
        for _ in range(i1):
            num = num * 10 + n3 % 10
            n3 //= 10
        result = n3 * (10 ** i1) + num
        return result if result <= (1 << 31) - 1 else -1

4.执行结果