> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/multiple-pointers/permutation/next-permutation.md).

# 31. Next Permutation

https\://leetcode.com/problems/next-permutation/description/

> Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
>
> If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
>
> The replacement must be in-place, do not allocate extra memory.
>
> Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

## Thoughts

下一个premutation比当前的大最小的那个，假定最后结果是fir之前的不用变，它应该被替换成它之后第一个比它大的数，然后它后面的数再从小到大排列。那这个fir就是从后面找到的第一个存在后面有比它大的数。具体实现方法为从后面找从尾往头遍历, 把第一个不满足升序的两个数的位置记下来. 再从尾往头遍历, 把第一个比nums\[i]大的数和nums\[i] swap一下. 这时i之后都是降序的, 再把它们反过来变成升序的即可。

> example: 6，3，4，9，8，7，1 此时 first ＝ 4，second = 9 从尾巴到前找到第一个大于first的数字，就是7 交换4和7，即上面的swap函数，此时序列变成6，3，7，9，8，4，1 再将second＝9以及以后的序列重新排序，让其从小到大排序，使得整体最小，即reverse一下（因为此时肯定是递减序列） 得到最终的结果：6，3，7，1，4，8，9

## Code

```
/*
 * @lc app=leetcode id=31 lang=cpp
 *
 * [31] Next Permutation
 */

// @lc code=start
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        const int N = nums.size();
        int i = N - 2;
        for (; i >= 0 && nums[i] >= nums[i + 1]; --i) continue;
        if (i >= 0) {
            for (int j = N - 1; j > i; --j) {
                if (nums[j] <= nums[i]) continue;
                swap(nums[i], nums[j]);
                break;
            }
        }
        reverse(nums.begin() + i + 1, nums.end());
    }
};
// @lc code=end


```

## Analysis

时间复杂度O(N), 空间O(1).