leetcode 031. 下一个排列

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

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