题目描述
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须[原地]修改，只允许使用额外常数空间。
例子：
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
官方难度
Medium
解题思路
没有思路，举例子找思路
176523 -->176532,
175632-->176532,
176791921-->176792119,
176543 -->314567,
貌似是从个位数字开始往前找，如果都比当前数字的最大数字大，则继续找，直到找到比当前最大数字小的位置，因为只有10个数字，我们可以用大小为10的数组来存储当前遍历有几位数，找到以后把比它大一点的数字放在该位置，剩余的进行排列，如果找到结尾都找不到就结束。
说不清楚思路，全靠举个例子：
- 输入
1767919221，初始化一个num[0] = 0, ..., num[9] = 0， max = 0 - 先看最后一位
1, num[1] += 1, max=1 - 看十位
2, 因为max<=2, 让max=2, num[2] += 1
4.继续看百位2, 因为max<=2, 让max=2, num[2] += 1 - 继续看千位
9因为max<=9,让max=9, num[9] += 1 - 继续看万位
1, 因为max=9>1,寻找num中比1大的数字，发现是2. - 修改万位
2. num[1] += 1, num[2] -=1，得到前几位176792 - 将数组中剩余的数字按照从大到小排序,加在
176792后面，为17679211229，结束。 - 如果到最后一位还没有找到，则直接排序。
然而测试用例有超过10的数字，所以这样不OK，新的解决思路如下：
上面的解决方案大体是对的，可以改一下
图片.png
代码如下：
class Solution(object):
def nextPermutation(self, nums):
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""
if len(nums) <= 1:
return nums
i = len(nums) - 2
while (i >= 0) and (nums[i+1] <= nums[i]):
i -= 1
if (i>=0):
j = len(nums) -1
while(nums[i] >= nums[j]):
j -= 1
temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
def reverse(nums, start):
end = len(nums) - 1
while(start < end):
temp = nums[start]
nums[start] = nums[end]
nums[end] = temp
start += 1
end -= 1
return nums
return reverse(nums, i+1)
# @lc code=end
