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