556 下一个更大元素 III

拼搏现实的明天。 2022-08-31 06:52 175阅读 0赞

**1. 问题描述：**

给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。

**示例 1：**

输入：n = 12  
输出：21

**示例 2：**

输入：n = 21  
输出：-1

**提示：**

1 <= n <= 2 ^ 31 - 1  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/next-greater-element-iii

**2. 思路分析：**

分析题目可以知道我们需要调整n中某些数字的顺序使得调整之后得到第一个大于n的最小的那个数字，如果不存在这样的数字那么返回-1，直观上说要想使得求得的数字是最小的，那么我们应该从n的低位开始调整，因为从低位开始调整数字的顺序所得到的数字变化幅度比较小，如果从高位开始调整那么变化会很大，这样得到的数字肯定不是最小的，所以我们应该从n的低位开始调整。因为使用的是python语言所以可以将n中的每一位存储到int类型的列表num中，方便后面操作。因为是从低位开始找第一个可以调整的位置所以我们需要逆序遍历num，如果上一个数字比当前位置的数字更大那么肯定是不可以调整的，也即当前的数字对应的位置到结尾都是逆序的，我们需要在循环中找到第一个不是逆序的位置i，这个时候说明i~len(num)位置的元素都是逆序的，然后我们需要找到i~len(num)中大于当前num\[i - 1\]的最小的那个数字的位置t，然后交换这两个数字的位置这样交换之后的列表对应的数字肯定是更大的，满足题目的条件，并且交换之后第i~len(num)的数字同样满足逆序，为了使得得到的数字是最小的所以需要翻转一下i~n位的数字这样得到的数字肯定是满足大于n的最小的数字。结合图会更好理解一点。

![20210723150920324.png][]

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        # 将n的每一位存储到列表中
        def getNum(self, n: int):
            res = list()
            while n:
                res.append(n % 10)
                n //= 10
            # 返回当前数字的列表表示, 由于添加到列表中的逆序所以先翻转一下[::-1]表示翻转列表元素
            return res[::-1]
    
        # 将int类型列表转为数字
        def toNum(self, num: List[int]):
            res = 0
            for i in range(len(num)):
                res = res * 10 + num[i]
            return res
    
        def nextGreaterElement(self, n: int) -> int:
            num = self.getNum(n)
            i = len(num) - 1
            # 逆序遍历找到第一个逆序的位置
            while i > 0 and num[i - 1] >= num[i]: i -= 1
            # 如果i=0之后说明肯定不存在答案
            if i == 0: return -1
            # 存在答案的情况下找到第一个大于num[i-1]的最小的那个数字
            t = i
            while t < len(num) and num[t] > num[i - 1]: t += 1
            # 交换两个位置的元素
            num[i - 1], num[t - 1] = num[t - 1], num[i - 1]
            # 翻转第i~n位的元素
            num[i:] = num[i:][::-1]
            res = self.toNum(num)
            # 这里需要判一下因为得到数字可能大于32位最大的整数2147483647
            if res > 2147483647: return -1
            return res

[20210723150920324.png]: /images/20220829/91e1bac0bdfb453ca13c5712a22c7aab.png