image.png

i从高到低遍历，尝试与右边比它最大的数当中离它最远的那个交换。

class Solution:
    def maximumSwap(self, nums: int) -> int:
        # 从头到尾交换
        begin=0
        ends=0
        num=[]
        while nums>0:
            num.append(int(nums%10))
            nums-=nums%10
            nums/=10
        num=num[::-1]
        rightstack=[]
        right = [-1 for i in range(len(num))]
        i=len(num)-1
        while i >=0:
            while len(rightstack)>0 and num[rightstack[-1]]<num[i]:
                rightstack.pop()
            if len(rightstack)>0:
                right[i]=rightstack[0]
            else:
                right[i]=-1
                # no need to swap
            rightstack.append(i)
            i-=1
        for i in range(len(num)):
            if right[i]!=-1 and num[right[i]]!=num[i]:
                num[i],num[right[i]]=num[right[i]],num[i]
                break
        n=0
        for i in range(len(num)):
            n*=10
            n+=num[i]
        return n