实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
思路：
124653 --> 125346
125430 --> 130245
从右向左找，只有找到前一位nums[i-1]小于当前位nums[i]的，排列后才可能比当前数字大；将nums[i-1]和右边找到的刚好大于nums[i-1]的数字作交换，最后把交换后的nums[i:]从小到大排列，保证结果最小，即nums[i:]倒序，因为交换后nums[i:]仍是从大到小。
class Solution:
def nextPermutation(self, nums):
n = len(nums)
for i in range(n - 1, 0, -1):
if nums[i-1] < nums[i]:
for j in range(n-1, i-1, -1):
if nums[j] > nums[i-1]:
nums[j], nums[i-1] = nums[i-1], nums[j]
nums[i:] = nums[i:][::-1]
return
else:
nums.reverse()
su = Solution()
nums = [3,2,1]
su.nextPermutation(nums)
print(nums)
class Solution(object):
def nextPermutation(self, nums):
""" :type nums: List[int] :rtype: void Do not return anything, modify nums in-place instead. """
if len(nums) <= 1:
return
idx = 0
for i in range(len(nums)-1, 0, -1):
if nums[i] > nums[i-1]: # find first number which is smaller than it's after number
idx = i
break
if idx != 0: # if the number exist,which means that the nums not like{5,4,3,2,1}
for i in range(len(nums)-1, idx-1, -1):
if nums[i] > nums[idx-1]:
nums[i], nums[idx-1] = nums[idx-1], nums[i]
break
nums[idx:] = nums[idx:][::-1]
