下一个排列

LeetCode 31 · Medium · 1 min · 榎aaaa

思路：找到下一个排序，意思就是将当前数组视作一串数字，通过对元素的重新组合，找到第一个大于当前数字的数字

具体实现：首先从后往前找到第一个逆序的数字，保存它的下标——如：123546718，这里会保存数字“4”的下标，也就是 4，之后再在 46718 这个范围内从后往前寻找第一个小于 5 的数字，并将其进行交换（123146758）；最后将46758进行降序·排序即可得到下一个排序

 1void nextPermutation(vector<int>& nums)
 2{
 3    int sz = nums.size();
 4    if(sz <= 1) return;
 5    int i = sz - 1;
 6    while(0 < i && nums[i] <= nums[i - 1])
 7    {
 8        i--;
 9    }
10
11    // 如果 i == 0，说明整个序列都是降序的（如 54321），已经是最大排列
12    if(0 < i)
13    {
14        int j = sz - 1;
15        while(nums[j] <= nums[i - 1])
16        {
17            j--;
18        }
19
20        std::swap(nums[i - 1], nums[j]);
21    }
22    std::sort(nums.begin() + i, nums.end());
23}