LC(分析)

题目大意

RT，输出下一个排列

解题思路

只有暴力思路，不会写。这种题都不会写。
分析：

1. 我们要把后面位上的大数与前面的小数交换，就能得到一个更大的数。
2. 增加的幅度要最小。
   1. 小数尽量是低位，所有从后往前找。
   2. 大数尽量小。
   3. 交换后。需要将大数后的位置为升序，升序是最小的排列。

疑问：
ij交换后，[i+1,end]一定是降序吗？
是的，因为较大值nums[j]也是从右往左找的，所以是大于nums[i]最小的j，j-1一定是大于j的。可得：

所以交换后不破环顺序，也是降序。

Code

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = nums.size()-2;
        while(i >= 0 && nums[i] >= nums[i+1]) {
            i--;            //找到第一个较小值nums[i]
        }
        if (i >= 0) { // 不是最后一个排列 
            int j = nums.size()-1; 
            while(j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums[i], nums[j]);
        }
        std::reverse(nums.begin()+i+1, nums.end());
    }
};