1 题目描述

下面是官方原题描述：

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

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

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

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

如果你没有听懂，那不该是你一个^-^,

翻译 过来就是这样的

找出这个数组排序出的所有数中，刚好比当前数大的那个数，不存在就返回最小的排列

刚拿到题的时候没有思路，后来写了几十行代码才发现思路已经不符合题意了-常数空间,参考了别人的答案；但是发现先很多题解要么太啰嗦要么太书面化，要么给了答案没说原因，看代码一知半解很是模糊。代码很容易看懂，单解释起来还是有些啰嗦

下面将非常详细地以大白话的形式从答案推题解——对于每一步的操作说出个所以然,而不是一个抽象的洋洋洒洒很多字讲不明白的，然后再正向推题解。

2 从答案推原因

先给出这题的答案(唯一):

存在的情况下：

从后往前遍历，寻找一个满足 nums[i]< nums[i+1] 一个下标 i，

从下标 i+1 到 end这段寻找一个数 nums[k]> nums[i](这里也是从后往前遍历)

交换 nums[k] 与nums[i]

最后翻转 nums[k+1:]

不存在：

将序列升序排序即可

重点再第一种情况,存在的情况下：

那么问题来了，为什么要从后往前遍历

我们寻找的是比原数大的一个，但是每次希望的是增幅尽量小；要让增幅尽量小，那么就尽量在低位进行操作，尽量保持高位不变。
为什么要寻找一个满足 nums[i]< nums[i+1] 一个下标 i？为什么要从下标 i+1 到 end这段寻找一个数 nums[k]> nums[i]

找i这个的目的就是寻找一个较小的数，可以看的出这个下标的右边都是降序排序，如果将右边内任意两个数进行swap，那么会比原来变的小，而我们寻找的是比原数大的。比如[1,2,7,4,3,1],我们进行第一步后，寻找到的下标为1，对应的值nums[1] = 2, 2右边任意两个数进行swap会比原来变的小

找到i后我们去在i的右边找一个刚刚好比nums[i]大的这个数，这个数比nums[i]大，但只好刚刚大一点，也就是说在大的情况下尽量小。

较小的数在前面，较大数在后面，这样交换后才会比原数大，这就是后面进行交换的原因。
为什么最后翻转 nums[k+1:]

nums[k+1:]是一个降序，但只有当它是纯升序时，这才更贴近原数(增幅小)

3 正向推题解

重点理解一下1，2步：

问题的本质是交换原序列中两个数以及施加可能的排序操作，使得变换后的序列刚刚好比原数大。

交换序列中两个数的过程中我们尽量要保证高位保持不变，低位进行交换操作，所有倒序遍历势在必行。

通过交换使得比原数大，那么就得在前面寻找一个小数，后面寻找一个大数。【大数与小数是两个之间相对来说得】。

那么问题又来了，这样交换可以使得变大，但是如何交换才能更加贴近原数，以及如何寻找这两个数呢？解决办法来了，从后往前遍历，找一个数 small_val 使得这个数得右边是个降序，然后在这个降序序列中又寻找一个刚刚好比small_val 大得数 big_val。交换。交换后将后面部分变为纯升序使得更加贴近原数。

4 源码


class Solution:
    def nextPermutation(self, nums) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """

        def reverse(nums, i, j):
            while i < j:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j -= 1

        small_index, big_index = -1, -1
        nums_len = len(nums)

        # 寻找较小数的下标
        for i in range(nums_len - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                small_index = i
                break

        # nums本身是一个降序排序， 不存在,对nums进行 原地排序
        if small_index == -1:
            nums.sort()
            return

        # 寻找较大 数的下标
        for i in range(nums_len - 1, small_index, -1):
            if nums[i] > nums[small_index]:
                big_index = i
                break

        # swap
        nums[small_index], nums[big_index] = nums[big_index], nums[small_index]

        # 后面进行sort
        reverse(nums, small_index + 1, nums_len - 1)
        return

    def main(self):
        nums = [1, 2, 3]
        self.nextPermutation(nums)
        print(nums)


if __name__ == '__main__':
    solution = Solution()
    solution.main()