下一个排列 图解题解

这道题真正在问什么

把数组原地重排成字典序里紧挨着它、刚好更大的那个排列，比如 [1,2,3] 的下一个是 [1,3,2]；如果它已经是这些数字的最大排列（完全降序，如 [3,2,1]），就回绕成最小排列（升序）。「刚好更大」四个字是全部难点：让排列变大很容易，让它变大得最少，才需要把排列的结构想清楚。

为什么从右往左找第一个升序对

想让一个数变大又涨幅最小，改动的位置应该尽量靠右——就像给数字加一要先动个位。从最右端往左看，只要相邻两数还是降序的，这一段就已经是这些数字能排出的最大值，在这段内部怎么折腾都变不大。第一个出现 nums[i] < nums[i+1] 的位置，就是从右数第一个「还有抬高余地」的位：它右边整段降序、已经到顶，所以下一个排列必须在这一位动手，且它左边的全部保持不动——若去动更左的位，跨过的排列就不止一个，得到的不再是「下一个」。

交换的对象为什么是刚好大一点的数

既然要抬高这一位，就得从它右边的后缀里挑一个比它大的数换上来；而为了整体「刚好更大」，要挑比它大的数里最小的那个。后缀恰好是降序的，所以从最右端往左遇到的第一个大于 nums[i] 的数就是目标，把两者交换即可。有重复元素时要注意判断的边界：查找时遇到小于等于 nums[i] 的都继续往左，保证不会选中相等的数——换一个相等的数等于没变大，排列原地踏步。

为什么交换之后还必须反转后缀

交换只完成了「抬高变动位」这半件事，此刻后缀仍是降序——换上去和换下来的两个数在大小上正好卡在原位的邻居之间，插回去不破坏降序——也就是说后缀还停在它的最大排列上。而我们要的是所有比原排列大的排列中最小的那个：变动位左边不动、变动位已定，后缀就应该取最小排列，即升序。后缀既然已是降序，用头尾双指针原地反转一遍就变成升序，这一步用 O(n) 的反转替代了排序，空间也保持 O(1)。

复杂度与三个常见翻车点

三个步骤各是一趟线性扫描或反转，时间 O(n)；全程只用几个下标原地交换，空间 O(1)。最常见的错：一是交换后忘了反转后缀，得到的排列比原来大得多、不是「下一个」；二是整个数组已完全降序、找不到升序对时，忘了把整体反转成升序而直接返回原数组；三是有重复元素时把第一步的判断写成严格大于就停，在相等处误停会选错位置——相等也要继续往左找。

Python

def nextPermutation(nums):
    n = len(nums)
    i = n - 2
    while i >= 0 and nums[i] >= nums[i+1]:  # ① 从右找第一个变小的位 i
        i -= 1
    if i >= 0:
        j = n - 1
        while nums[j] <= nums[i]:           # ② 从右找刚好比 nums[i] 大的 j
            j -= 1
        nums[i], nums[j] = nums[j], nums[i] # 交换
    lo, hi = i + 1, n - 1                   # ③ 反转 i 后面的后缀
    while lo < hi:
        nums[lo], nums[hi] = nums[hi], nums[lo]
        lo += 1; hi -= 1

C++

void nextPermutation(vector<int>& nums){
    int n = nums.size(), i = n - 2;
    while(i >= 0 && nums[i] >= nums[i+1]) i--;   // ① 找变小位 i
    if(i >= 0){
        int j = n - 1;
        while(nums[j] <= nums[i]) j--;           // ② 找刚好更大的 j
        swap(nums[i], nums[j]);                  // 交换
    }
    reverse(nums.begin() + i + 1, nums.end());   // ③ 反转后缀
}

Java

public void nextPermutation(int[] nums) {
    int n = nums.length, i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;   // ① 找变小位 i
    if (i >= 0) {
        int j = n - 1;
        while (nums[j] <= nums[i]) j--;            // ② 找刚好更大的 j
        int t = nums[i]; nums[i] = nums[j]; nums[j] = t; // 交换
    }
    int lo = i + 1, hi = n - 1;                    // ③ 反转后缀
    while (lo < hi) {
        int t = nums[lo]; nums[lo] = nums[hi]; nums[hi] = t;
        lo++; hi--;
    }
}