LeetCode 31. 下一个排列

◎

本节目标

从右侧找到可增大的拐点，用最小增量交换后恢复最小后缀。

查看 LeetCode 原题

题意与边界

在原数组中构造字典序严格更大的最小排列；若当前排列已经最大，则变成字典序最小排列。只能使用常数辅助空间。

最小幅度增大

从右向左寻找第一个满足 nums[pivot] < nums[pivot + 1] 的位置，其右侧必为非递增后缀。再从最右端寻找第一个严格大于枢轴的值并交换，这会让高位产生最小可能增量。交换后把后缀反转成升序，得到该高位选择下的最小后缀。

正确性依据

最右侧可增大的位置让更高位全部保持不变，因此任何更靠左的改变都会产生更大的字典序跳跃。非递增后缀中从右侧找到的第一个较大值是可用于交换的最小值；反转后缀则给出剩余元素的最小排列。若不存在枢轴，整个数组非递增，反转后就是全局最小排列。

代码实现

C++

C++17

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int pivot = static_cast<int>(nums.size()) - 2;
        while (pivot >= 0 && nums[pivot] >= nums[pivot + 1]) {
            pivot--;
        }
        if (pivot >= 0) {
            int successor = static_cast<int>(nums.size()) - 1;
            while (nums[successor] <= nums[pivot]) {
                successor--;
            }
            swap(nums[pivot], nums[successor]);
        }
        reverse(nums.begin() + pivot + 1, nums.end());
    }
};

Python

Python 3

class Solution:
    def nextPermutation(self, nums: list[int]) -> None:
        pivot = len(nums) - 2
        while pivot >= 0 and nums[pivot] >= nums[pivot + 1]:
            pivot -= 1
        if pivot >= 0:
            successor = len(nums) - 1
            while nums[successor] <= nums[pivot]:
                successor -= 1
            nums[pivot], nums[successor] = nums[successor], nums[pivot]

        left = pivot + 1
        right = len(nums) - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(1)，后缀使用双指针原地反转。

易错点

• 枢轴比较未使用严格关系，重复值时选择错误。
• 从左侧寻找交换值，未取得后缀中最小的严格较大值。
• 交换后对后缀排序或切片，破坏常数辅助空间要求。

模式迁移

构造“刚好更大”的序列通常分成两步：在尽量靠右的位置制造最小增量，再把低位恢复为最小状态。这个思想也适用于下一个更大整数和排列枚举。