Problem: 31. 下一个排列

思路

两次遍历后交换位置，降序变升序；

解题方法

1.解决方法：二次遍历，时间复杂度：$O(N)O(N)$,空间复杂度为 $O(1)O(1)$；

Code

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i=nums.size()-2;
        while(i>=0&&nums[i]>=nums[i+1])//第一次遍历，从后往前找到降序前一个小一些的数，设为基准
        {
            --i;
        }
        int j=nums.size()-1;
        if(i>=0)
        {
             while(j>0&&nums[j]<=nums[i])//第二次遍历，从后往前找到降序中略小于基准数的数字
            {
                --j;
            }
            swap(nums[i],nums[j]);  //交换两个数字
        }

        reverse(nums.begin()+i+1,nums.end());//同一个数组降序大于升序，翻转降序部分
    }
};