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

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

链接： https://leetcode-cn.com/problems/next-permutation

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = nums.size() - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.size() - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums[i], nums[j]);
        }
        reverse(nums.begin() + i + 1, nums.end());
    }
};

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void print(vector<int> nums) {
    for (auto i : nums) {
        cout << i << ' ';
    }
    cout << endl;
}

int main() {
    vector<int> nums = {4, 5, 2, 6, 3, 1};
    //vector<int> nums = {4, 3, 2, 1};
    print(nums);
    // 从后往前找生序对
    int i = nums.size() - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        cout << "i=" << i << " " << nums[i] << endl;
        i--;
    }
    cout << "i=" << i << " " << nums[i] << endl;
    // 找比nums[i]大的
    if (i >= 0) {
        int j = nums.size() - 1;
        while (j >= 0 && nums[i] >= nums[j]) {
            cout << "j=" << j << " " << nums[j] << endl;
            j--;
        }
        cout << "j=" << j << " " << nums[j] << endl;
        swap(nums[i], nums[j]);
    }
    print(nums);
    //
    reverse(nums.begin() + i + 1, nums.end());
    print(nums);
    return 0;
}