【LeetCode Hot 100】31. 下一个排列

louistang0524 / 2024-10-15 / 原文

https://leetcode.cn/problems/next-permutation/description/

这里下个排列的意思是按字典序的排列，C++ STL中算法默认也是按照字典序排列来操作。C++ STL中提供了对应的接口next_permutation，下面记录一下力扣给的题解，这种方法允许数据重复，据说STL也是采用的这种方法。

从后向前查找第一个相邻的升序元素对(i,j)，它们满足nums[i]<nums[j]，此时[j,end)必然是降序。如果找不到符合要求的升序元素对，说明当前整个序列是降序，直接跳到步骤4。
在[j,end)中从后往前查找第一个满足nums[i]<nums[k]的k。
将nums[i]与nums[k]交换。
可以断定此时[j,end)必然是降序，翻转[j,end)元素，使其变成升序。

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) {
            return;
        }

        int i = n - 2, j = n - 1, k = n - 1;
        while (i >= 0 && nums[i] >= nums[j]) {
            i--, j--;
        }
        if (i >= 0) {
            while (nums[i] >= nums[k]) {
                k--;
            }
            swap(nums[i], nums[k]);
        }

        // reverse nums[j:end]
        reverse(nums.begin() + j, nums.end());
    }
};