题解 | #下一个排列#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector
     */
    vector<int> nextPermutation(vector<int>& nums) {
        // write code here
        int n = nums.size();
        if (n <= 1) return nums;

        // 先从后往前找第一个相邻升序元素对 (i, i + 1)，满足 nums[i] < nums[i + 1]
        // 找的是待交换的较小元素
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        // i 不在开头，表明整个数组不是完全的降序排列的
        if (i >= 0) {
            // 再从后往前找第一个大于 nums[i] 的元素 nums[j]
            // 找的是待交换的另一个元素，比前面找到的元素大的最小元素
            int j = n - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            // 都找到了就直接交换
            swap(nums[i], nums[j]);
        }

        // 我们前面从后往前找到了第一个相邻升序元素对，元素对后面的排列必然是降序的，
        // 我们需要的是字典序的下一个，自然要把后面改成升序的。
        reverse(nums.begin() + i + 1, nums.end());
        // 如果 i == 0，这意味着整个数组从头到尾全是降序，这就是字典序最大的那个排列，
        // 要返回最小的数组排列，其实和上面也是一样的
        return nums;
    }
};