leetcode556 下一个更大元素 III

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

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

解答：
方法一：

class Solution:
    def nextGreaterElement(self, n: int) -> int:
        if n>=2**31-1:
            return -1
        nums=[]
        while n:
            nums.append(n%10)
            n//=10
        nums=nums[::-1]
        m=len(nums)
        flag=False
        #寻找最后一对正序对，并交换他们的位置，即为答案
        for i in range(m-2,-1,-1):
            #注意此处要逆序
            for j in range(m-1,i,-1):
                if nums[j]>nums[i]:
                    nums[i],nums[j]=nums[j],nums[i]
                    nums[i+1:]=sorted(nums[i+1:])
                    flag=True
                    break
            if flag:
                break
        if not flag:
            return -1
        #还原n
        cur=0
        for i in range(m):
            cur=cur*10+nums[i]
        #print(cur)
        if cur>2**31-1:
            return -1
        else:
            return cur
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

方法二：转化简化

class Solution:
    def nextGreaterElement(self, n: int) -> int:
        nums = [int(x) for x in str(n)]
        #当前数已经为逆序排列，即已经是最大数了
        if sorted(nums)[::-1] == nums:
            return -1
        m=len(nums)
        flag=False
        #寻找最后一对正序对，并交换他们的位置，即为答案
        for i in range(m-2,-1,-1):
            for j in range(m-1,i,-1):
                if nums[j]>nums[i]:
                    nums[i],nums[j]=nums[j],nums[i]
                    #将i之后的逆序对调整为正序
                    nums[i+1:]=sorted(nums[i+1:])
                    flag=True
                    break
            if flag:
                break
        if not flag:
            return -1
        #还原n
        cur=0
        for i in range(m):
            cur=cur*10+nums[i]
        if cur>2**31-1:
            return -1
        else:
            return cur
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30