leetcode 下一个排列 中等

本文主要是介绍leetcode 下一个排列 中等，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

生成下一个排列的方法：从右往左找到第一个存在左边有比其小的数的两下标，假设分别为 l，r。

如：1 2 3 5 4 1 0，最后位置的 0 左边没有比他小的数，倒数第二个 1 左边没有比他小的数，4 左边比他小的数为 3，即 l = 2。

此时 l = 2 与 r = 4 交换，得到 1 2 4 5 3 1 0，将 [l + 1, nums.size() - 1] 进行反序，1 2 4 0 1 3 5 即为下一个排列。

所以最关键的是找 l 和 r。有两种方案：

1、单调栈，从后往前维护递增，当出现第一次弹栈的时候，即位置 l，而最后一个被弹出的，即位置 r

2、从后往前，找两个相邻的位置 i 和 i + 1，使得 nums[i] < nums[i + 1]，此时的 位置 i 即为 l，再次从后往前，找到第一个大于 nums[i] 的数，即为位置 r

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if(nums.empty()) return ;
        int l = nums.size() - 1, r = -1;
        for(int i = l - 1; i >= 0; -- i, -- l) {
            if(nums[i] < nums[l]) {
                r = nums.size() - 1;
                while(nums[r] <= nums[i]) -- r;
                swap(nums[i], nums[r]);
                reverse(nums, l, nums.size() - 1);
                return ;
            }
        }
        reverse(nums, 0, nums.size() - 1);
    }

    void reverse(vector<int> &nums, int l, int r) { // [l, r] 翻转
        for(int i = l, j = r; i < j; ++ i, -- j) {
            swap(nums[i], nums[j]);
        }
    }
};

这篇关于leetcode 下一个排列 中等的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！