题目内容

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须 原地 修改，只允许使用额外常数空间。

示例

示例 1：

输入：nums = [1,2,3]
输出：[1,3,2]

示例 2：

输入：nums = [3,2,1]
输出：[1,2,3]

示例 3：

输入：nums = [1,1,5]
输出：[1,5,1]

示例 4：

输入：nums = [1]
输出：[1]

提示

1 <= nums.length <= 100
0 <= nums[i] <= 100

题解

本题是一道求按照升序字典序排列的下一个排列的问题。我们有如下思考：

1、要尽量保持高位不变，尽量移动低位数字求解

2、如果nums从第k位开始到结尾是一个非升序的序列，那么可得出要移动的位置不在第k位开始到末尾的区间内，因为第k位的数字是这个区间内的最大值，在这个区间内用任意数字交换第k位的数都会变小。

3、具体思路是：从右开始找到nums的第一个非降序的位置，假设为第i位，然后从该位置往右找到一个比该数大的最小数，假设在第j位，然后交换nums[i]和nums[j]。然后，将第i位置后面的数重新进行升序排列即可。

4、注意如果第k位到了0，也就意味着nums整个是一个降序的序列，也就意味着nums的排列是字典序的最大。题目要求，如果给出的是字典序的最大排列，则返回字典序的最小排列，因此直接将nums倒序后返回即可。

代码

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        //从末尾往前遍历，找到第一个非降序的位置，然后从该位置往后找到一个比该数大的最小数，然后交换位置后，将后续的点从新排列为升序即可。
        int k = nums.size() - 1;
        while(k > 0 && nums[k - 1] >= nums[k]) k--;//找到第一个非降序的位置
        if(k <= 0){
            reverse(nums.begin(),nums.end());
        }else{
            int t = k;
            while(t < nums.size() && nums[t] > nums[k - 1]) t++;
            swap(nums[t - 1],nums[k - 1]);
            reverse(nums.begin() + k, nums.end());
        }
    }
};