📝 题目描述

题目链接：下一个排列

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

  • 例如，arr = [1,2,3]，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

  • 例如，arr = [1,2,3] 的下一个排列是 [1,3,2]。
  • 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2]。
  • 而 arr = [3,2,1] 的下一个排列是 [1,2,3]，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums，找出 nums 的下一个排列。

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

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例 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 <= nums.length <= 100
  • 0 <= nums[i] <= 100

💡 解题思路

方法一：两遍扫描

这道题的核心是：让排列变大，同时让它尽可能小地变大。

字典序比较的是从左往右，第一个不同的位置。所以，我们要尽量保留左边的元素，把变化留在右边。把思路拆成三步：找到要增大的位置、换成稍大的数、把后面变成最小排列。

  1. 从右往左，找到第一个 nums[i] < nums[i + 1] 的位置。
    以 nums = [1,3,5,4,2] 为例，末尾的 [5,4,2] 已经是不递增顺序，也就是这些元素能组成的最大排列。只调整这三个元素，无法让整个数组变大。因此，必须动到前面的 3。它就是我们要增大的位置 i。更一般地，找到这个位置后，i 右边的整个后缀一定是不递增的。这里说“不递增”，是因为相邻元素也可能相等。

  2. 在右边找到比 nums[i] 大的最小元素，交换它们。
    为了只增大一点点，示例中的 3 应该换成 4，而不是 5。后缀已经从大到小排列，所以从最右边往左，找到的第一个严格大于 nums[i] 的数，就是我们要的数，记它的位置为 j。

  3. 反转 i 右边的整个后缀。
    交换后，数组已经比原来大了。现在应该把后面的元素排成升序，让结果尽可能小。这里有一个巧妙之处：按上面的规则交换后，后缀仍然是不递增的，因此直接反转就能得到升序，无须排序。

上面的步骤能保证正确，是因为我们依次保证了：变化的位置尽可能靠右，这个位置的数增大得尽可能少，剩余后缀尽可能小。如果第一步找不到 i，说明整个数组都不递增，已经是最大排列。例如 [3,2,1]，直接反转整个数组即可。

🔧 代码实现

1、两遍扫描

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = 0, j = 0, n = nums.size();
        for (i = n - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                break;
            }
        }
        if (i >= 0) {
            for (j = n - 1; j > i; j--) {
                if (nums[j] > nums[i]) {
                    break;
                }
            }
            swap(nums[i], nums[j]);
            reverse(nums.begin() + i + 1, nums.end());
        } else {
            reverse(nums.begin(), nums.end());
        }
    }
};

📊 复杂度分析

1、两遍扫描

  • 时间复杂度：O(n)O(n)，其中 nn 为给定序列的长度，我们至多只需要扫描两次序列，以及进行一次反转操作。
  • 空间复杂度：O(1)O(1)，只需要常数的空间存放若干变量。

🎯 总结

  • 核心思想：技巧类题目，记住即可。