31. 下一个排列
思路
首先说一下什么是字典序，把1 2 3当作a b c的话，abc有6种排列顺序。
abc acb bac bca cab cba
上图就是字典序，题目的要求狠简单： 找到下一个字典序，如果没有的话，则输出最小的序号。
首先明确一下，没有下一个序列的情况，那么就是大的全部在前面，所以只需要反转数组就行，就可以回到最小的序列。
再看有下一个排序的情况，我们需要先从右侧找到一个比最右边数字小的数.
然后再和右边第一个大于这个数的数进行交换，以571632为例子：
第一个小于右侧数字的数是1，第一个大于1的数字是2，交换之后:
572631, 由于之前确定的，是通过升序找到的1，所以还需要反转2后面的数字: 572136 就是最终结果了！
正好可以和上面反转的一起处理。
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 左侧的第一个非升序数字，这里也可以len(nums)-2
j = len(nums)-1
while j-1 >= 0:
if nums[j] > nums[j-1]:
break
j -= 1
# 如果j-1>=0说明找到了这个数字，否则说明数组
# 是降序排列的
if j-1 >= 0:
right = len(nums)-1
# 找到右边第一个大于nums[j-1]的数字
while right > j-1 and nums[right] <= nums[j-1]:
right -= 1
# 交换他们
nums[j-1], nums[right] = nums[right], nums[j-1]
self.reverse(nums, j, len(nums)-1)
else:
self.reverse(nums, 0, len(nums)-1)
# 反转数组
def reverse(self, nums, i, j):
while i < j:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
return nums
