题目描述

在这里插入图片描述

在这里插入图片描述

解题思路

在这里插入图片描述

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
private:
    //反转降序的后部分
    void reverse(vector<int>& nums, int left, int right)
    {
        while(left < right)
        {
            swap(nums[left++], nums[right--]);
        }
    }
public:
    void nextPermutation(vector<int>& nums) {

        int len = nums.size();
        if (len < 1) return;
        //反遍历，找到非降序的首元素
        int i = len - 2;
        while (i >= 0 && nums[i] >= nums[i + 1])
        {
            --i;
        }
        if (i >= 0)
        {
            int j = len - 1;
            while (j >= 0 && nums[j] <= nums[i])
            {
                --j;
            }
            swap(nums[i], nums[j]);
        }
        reverse(nums ,i + 1, len - 1);
    }
};