算法题-下一个排列

算法

Created At : 2023-09-16 12:36

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

首先, 如果要找下一个排列的话, 当前给定的数组中, 前面位置的元素尽量不要变, 终点要变后面位置的元素.

从后向前扫描元素, 如果元素是升序(大于等于)的话, 那么其实是没法动的, 我们的目的是从后向前找到第一个降序的位置$k$, 使得nums[k - 1] < nums[k].

此时, 从k到数组结尾, 选择一个大于nums[k - 1]的最小值, 和nums[k - 1]互换一下位置, 然后将k后面的数组部分逆序一下, 就得到了下一个排列.

例如排列2, 1, 3, 5, 4, 此时k = 3, nums[k] = 5, 后面大于nums[k - 1] 的最小值是4, 那么最终得到的排列就是2, 1, 4, 3, 5.

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int k = nums.size() - 1;
        while (k > 0 && nums[k - 1] >= nums[k]) k --;

        // 整个nums数组完全降序
        if (k == 0)
        {
            reverse(nums.begin(), nums.end());
        }
        else 
        {
            int t = k;
            while (t < nums.size() && nums[t] > nums[k - 1]) t ++;
            // t位置是第一个小于等于nums[k - 1], 那么t-1就是第一个大于nums[k - 1]的位置
            swap(nums[t - 1], nums[k - 1]);
            reverse(nums.begin() + k, nums.end());
        }
    }
};