1. 题目

Next Permutation

2. 算法

• stl
• 逆序

例如：1 4 6 5 3 2

step1:从右往左找到第一个破坏升序的元素，例如：4，标记为i；

step2:依次从右往左找第一个大于4的元素，例如：5，交换4和5

step3:从i+1到最右端，逆置。6432->2346

So,152346为所求

3. 代码

3.1 stl

class Solution{
public:
    void nextPermutation(vector<int>& nums){
        next_permutation(nums.begin(),nums.end());
    }
};

逆序

class Solution{
public:
    void nextPermutation(vector<int>& nums){
        if(!nums.size())
            return;
        int idx=nums.size()-2;

// 找到第一个乱序s
        while(idx>=0 && nums[idx]>=nums[idx+1])
            idx--;

// 交换
        if(idx>=0){
            int i=idx+1;
            while(i<nums.size()&& nums[i]>nums[idx])
                i++;
            swap(nums[i-1],nums[idx]);
        }

//反转
        reverse(nums.begin()+idx+1,nums.end());
      }   
};