leetcode 链接：下一个排列

题目

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

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

示例：

输入：nums = [1,2,3]
输出：[1,3,2]

输入：nums = [3,2,1]
输出：[1,2,3]

输入：nums = [1,1,5]
输出：[1,5,1]

输入：nums = [1]
输出：[1]

解答 & 代码

• 要使得排列的字典序变大，那么要将一个左边的“较小数”和右边的“较大数”交换
• 要得到下一个排列，那么不能变大太多，因此要找到一个最靠右的“较小数”，再找到尽可能小的“较大数”和它交换，交换完后，较大数右边的序列应该逆序（原本是降序的，改为升序）

class Solution {
    // 交换数组 idx1 和 idx2 未知的两个元素
    void swap(vector<int>& nums, int idx1, int idx2)
    {
        int temp = nums[idx1];
        nums[idx1] = nums[idx2];
        nums[idx2] = temp; 
    }
    // 将数组的 left 到 right 区间（含两端）逆转
    void reverse(vector<int>& nums, int left, int right)
    {
        while(left < right)
        {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            ++left;
            --right;
        }
    }
public:
    void nextPermutation(vector<int>& nums) {
        int len = nums.size();
        if(len <= 1)
            return;

        // 1. 从后往前找到第一个 nums[i] < nums[i+1] 的位置 i
        int i = len - 2;
        while(i >= 0 && nums[i] >= nums[i + 1])
            --i;
        // 2. 如果找到 i，从后往前找到第一个位置 j，使得 nums[i] < nums[j]
        // 交换 nums[i] 和 nums[j]
        if(i >= 0)
        {
            int j = len - 1;
            while(j > i && nums[i] >= nums[j])
                --j;
            swap(nums, i, j);
        }
        // 3. 将 nums[i + 1]~nums[len-1] 逆序
        reverse(nums, i + 1, len - 1);
    }
};

执行结果：

执行结果：通过

执行用时：8 ms, 在所有 C++ 提交中击败了 38.96% 的用户
内存消耗：11.9 MB, 在所有 C++ 提交中击败了 5.53% 的用户