遇到输入序列就是严格降序的，直接返回其升序。 从右往左找到第一对两个连续的数字 a[i] 和 a[i+1]，它们满足 a[i]<a[i+1]（从后往前找）。此时交换这两个数字，就能得到一个比原来序列更大的组合。接着，去a[i+1]右边找到一个a[j]（从后往前找），使得a[j-1]<a[i]<a[j]。这时，交换a[i-1]和a[j]，再对a[i]右边的数字进行一次降序排列，就可以了得到结果了。

题目

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
人话版问题描述：给定若干个数字，将其组合为一个整数。如何将这些数字重新排列，以得到下一个更大的整数。如 123 下一个更大的数为 132。如果没有更大的整数，则输出最小的整数。

示例

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

考察知识点

数组

核心思想

方法一、 暴力破解法

算法
在这种方法中，我们找出由给定数组的元素形成的列表的每个可能的排列，并找出比给定的排列更大的排列。 但是这个方法是一种非常天真的方法，因为它要求我们找出所有可能的排列 这需要很长时间，实施起来也很复杂。 因此，这种方法根本无法通过。 所以，我们直接采用正确的方法。

复杂度分析
时间复杂度：\(O(n!)\)，可能的排列总计有 n! 个。 空间复杂度：\(O(n)\)，因为数组将用于存储排列。

方法二、扫描法

代码概述：
1、特判：遇到输入序列就是严格降序的，直接返回其升序。
2、如果输入序列不是严格降序，从右往左找到第一对两个连续的数字 a[i] 和 a[i+1]，它们满足 a[i]<a[i+1]（从后往前找）。此时交换这两个数字，就能得到一个比原来序列更大的组合，但是，题目要求得到的是下一个不能太大，也就刚好比当前组合大，直接交换a[i]和a[i+1]，得到的满足不了条件。如：

输入：
[1,3,2]
错误输出：
[3,1,2]
正确输出：
[2,1,3]

3、那要怎么办呢？此时我们知道，a[i+1]右边肯定是严格降序的，否则a[i]不会是第一个满足a[i]>a[i+1]条件的数字，那么就去a[i+1]右边找到一个a[j]（从后往前找），使得a[j-1]<a[i]<a[j]。
4、这时，交换a[i-1]和a[j]，再对a[i]右边的数字进行一次降序排列，就可以了得到结果了。

整个过程如下：

方法三、D.E. Knuth 算法（待补充）

按照字典顺序生成全排列，在 \(O(N)\) 时间内解决该问题。

Python版本

简单写了一个版本

把问题思考的太简单。通过测试用例 154 / 265。

class Solution:
    def nextPermutation(self, nums: list) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if len(nums) == 0:
            return []
        tmp_nums = list(nums)
        # tmp_nums.reverse()
        tmp_nums.sort(reverse=True)
        if tmp_nums == nums:
            nums.sort()
        else:
            max_index = 0
            for i in range(len(nums)-1):
                if nums[i] < nums[i+1] and i > max_index:
                    max_index = i
            
            # swape
            tmp_num = nums[max_index] 
            nums[max_index] = nums[max_index + 1]
            nums[max_index + 1] = tmp_num

扫描法实现

class Solution:
    def swape(self, nums, i, j):
        tmp = nums[i]
        nums[i] = nums[j]
        nums[j] = tmp

    def reverse(self, nums, start):
        i = start
        j = len(nums) - 1
        while i < j:
            self.swape(nums, i, j)
            i += 1
            j -= 1

    def nextPermutation(self, nums: list) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums_len = len(nums)
        if nums_len == 0:
            return []
        tmp_nums = list(nums)
        tmp_nums.sort(reverse=True)
        if tmp_nums == nums:
            nums.sort()
        else:
            i = nums_len - 2
            while i >= 0 and nums[i+1] <= nums[i]:  # 从后往前找 找一个后面大于前面数字的位置 i
                i -= 1
            if i >= 0:
                j = nums_len - 1
                while j >=0 and nums[j] <= nums[i]:  # 从后往前找 找一个比nums[i]要小的位置
                    j -= 1
                self.swape(nums, i, j)  # 交换nums[i]和nums[j]
            self.reverse(nums, i + 1)

            # # 不能用for循环。 用for循环调了很久，没有调出来。当i就在倒数第二个的时候，for j in range(nums_len-1, i+1, -1)根本执行不了，j也就找不到。更不会进行正常处理。还是尽量用while吧。
            # for i in range(nums_len-2, -1, -1):  # find i 从后往前
            #     if nums[i] < nums[i+1]:
            #         break
            # if i >= 0:
            #     for j in range(nums_len-1, i+1, -1):  # find j 用for循环的话，输入样例是[1, 2, 3]时，j就找不到，就不赋值了。所以不能用for循环。
            #         if nums[j] > nums[i]:
            #             break
            #     # swape
            #     self.swape(nums, i, j)
            # # reverse back part of list
            # self.reverse(nums, i + 1)

时间复杂度：\(O(n)\)，在最坏的情况下，只需要对整个数组进行两次扫描。
空间复杂度：\(O(1)\)，没有使用额外的空间，原地替换足以做到。
执行用时 :44 ms, 在所有 Python3 提交中击败了77.95%的用户
内存消耗 :13.3 MB, 在所有 Python3 提交中击败了31.28%的用户

有效语法糖

能用while就别用for来控制循环，for循环的启动也是有条件的。