题目描述

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须[原地]修改，只允许使用额外常数空间。

例子：

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
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