31. 下一个排列

题目链接（中等）

题目描述

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

以数字序列 [1,2,3] 为例，其排列按照字典序依次为：

[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]

排列 [2,3,1] 的下一个排列为 [3,1,2]；最大的排列 [3,2,1] 的下一个排列为最小的排列 [1,2,3]。

给你一个整数数组 nums，找出 nums 的下一个排列。必须 原地 修改，只允许使用额外常数空间。

数据范围：1 ≤ nums.length ≤ 100，0 ≤ nums[i] ≤ 100

示例

示例 1：

输入： nums = [1,2,3]
输出： [1,3,2]

示例 2：

输入： nums = [3,2,1]
输出： [1,2,3]

示例 3：

输入： nums = [1,1,5]
输出： [1,5,1]

方法一：两遍扫描

思路及解法

直觉上，我们希望尽量保留前面的数字不变，只在最靠右的位置让数字变大一点点。因为右边部分是降序的，它已经是这些数字能组成的最大排列，无法通过内部调整再变大；所以必须找到一个左边的“较小数”，用右边比它大的最小数替换它，再把右边重新排成升序（即最小排列），这样得到的就是下一个排列。

下一个排列总是比当前排列大（除非已是最大），我们希望变大的幅度尽可能小：

1. 将一个左边的「较小数」与一个右边的「较大数」交换，使排列变大；
2. 「较小数」尽量靠右，「较大数」尽可能小；交换后，把「较大数」右边的数升序重排，使变大幅度最小。

对长度为 n 的排列 a：

1. 从后向前找第一个顺序对 (i, i+1) 满足 a[i] < a[i+1]，「较小数」即 a[i]，此时 [i+1, n) 必然是下降序列；
2. 在 [i+1, n) 中从后向前找第一个 j 满足 a[i] < a[j]，「较大数」即 a[j]；
3. 交换 a[i] 与 a[j]，此时 [i+1, n) 必为降序，直接用双指针反转该区间使其升序，无需排序。

若步骤 1 找不到顺序对，说明整个序列是降序（最大排列），跳过步骤 2 直接执行步骤 3，得到最小的升序序列。

该方法支持重复元素，C++ 标准库的 next_permutation 即采用此实现。

代码

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
            
        if i >= 0:
            j = n - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]

        l, r = i + 1, n - 1
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1

复杂度分析

• 时间复杂度：$O(n)$，至多两次扫描加一次反转。
• 空间复杂度：$O(1)$，只使用常数个变量。