LeetCode 31. 下一个排列

题目类型

1. 数组
2. 找规律题

题目链接

https://leetcode.cn/problems/next-permutation/

思路

建议画图用例子模拟

[2 3 5 4 1] => [2 4 1 3 5]

1. 先用指针k从后往前找，找到第一个不满足nums[k - 1]>nums[k]的位置，即k即往后的都为降序
2. 如果k在nums起始位置，则将整个数组反转，否则执行3
3. 用指针t从指针k所在位置往右寻找，找到第一个大于nums[k-1]的数,此时整个数为nums[t - 1]
4. 并且将nums[k-1]和nums[t - 1]互换
5. 将k后面的序列反转

AC代码

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int k = nums.size() - 1;
        // 2 3 5 4 1
        // 此时处于5这个位置
        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() - 1 && nums[t] > nums[k - 1]) t ++;
            swap(nums[k - 1], nums[t - 1]);
            reverse(nums.begin() + k, nums.end());
        }
    }
};