题目

解法：双指针

思路

核心思想是从数组末尾向前寻找第一个满足 nums[i] < nums[i+1] 的位置 i，然后交换 nums[i] 与后面大于它的最小元素，并反转后缀以获得下一个排列。

该方法正确是因为：若整个数组降序，则无更大排列，反转得最小；否则，i 是最后一个可增大的位置，后缀为降序。交换 nums[i] 与大于它的最小元素（从后往前找第一个大于的）确保增大最小幅度，反转后缀使其升序得到最小后缀，从而整体为紧挨着的下一个排列。

• Step 1: 从后向前遍历，寻找第一个满足 nums[i] < nums[i+1] 的索引 i。
• Step 2: 若找到，从末尾向前寻找第一个大于 nums[i] 的元素索引 j。
• Step 3: 交换 nums[i] 和 nums[j]。
• Step 4: 反转子数组 nums[i+1..end] 使其升序。
• Step 5: 若未找到 i，反转整个数组。

复杂度

• 时间复杂度: $O(n)$，其中 n 是数组长度，最坏情况下需要遍历数组两次并执行一次反转操作。
• 空间复杂度: $O(1)$，仅使用常数级别的额外空间存储索引和临时变量。

代码

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

        }
        reverse(nums.begin(), nums.end());
    }
};