'''
求下一个字典序,使用经典的算法
'''
class Solution:
def nextPermutation(self, nums) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
if len(nums)<=1:
return
flag=False # 表示现在还没有找到反向扫描过程中的降序对
i=len(nums)-1
for i in range(len(nums)-1,0,-1):
if nums[i]>nums[i-1]:
flag=True
break
if flag==False:# 表示反向扫描阶段，遇到的都是升序对，说明已经到达全排列的最后一个数
nums.sort()
return
index_left=i-1
j=len(nums)-1
for j in range(len(nums)-1,index_left,-1):
if nums[j]>nums[index_left]:
break
index_right=j
temp=nums[index_left]
nums[index_left]=nums[index_right]
nums[index_right]=temp
# print(index_left,index_right)
nums[(index_left+1):]=nums[(index_left+1):][::-1]
if __name__=="__main__":
Solution().nextPermutation([3,2,1])
