# 0031. 下一个排列
### 题目地址(31. 下一个排列)
### 题目描述
```
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
```
### 前置知识
* 回溯法
### 公司
* 阿里
* 腾讯
* 百度
* 字节
### 思路
符合直觉的方法是按顺序求出所有的排列，如果当前排列等于 nums，那么我直接取下一个但是这种做法不符合 constant space 要求（题目要求直接修改原数组）,时间复杂度也太高，为 O(n!),肯定不是合适的解。
我们也可以以回溯的角度来思考这个问题，即从后往前思考。
让我们先回溯一次，即思考最后一个数字是如何被添加的。
由于这个时候可以选择的元素只有 2，我们无法组成更大的排列，我们继续回溯，直到如图：
我们发现我们可以交换 4 和 2 就会变小，因此我们不能进行交换。
接下来碰到了 1。 我们有两个选择：
* 1 和 2 进行交换
* 1 和 4 进行交换
两种交换都能使得结果更大，但是 和 2 交换能够使得增值最小，也就是题目中的下一个更大的效果。因此我们 1 和 2 进行交换。
还需要继续往高位看么？不需要，因为交换高位得到的增幅一定比交换低位大，这是一个贪心的思想。
那么如何保证增幅最小呢? 其实只需要将 1 后面的数字按照从小到大进行排列即可。
注意到 1 后面的数已经是从大到小排列了（非严格递减），我们其实只需要用双指针交换即可，而不需要真正地排序。
> 1 后面的数一定是从大到小排好序了吗？当然，否则，我们找到第一个可以交换的回溯点就不是 1 了，和 1 是第一个可以交换的回溯点矛盾。因为第一个可以交换的回溯点其实就是从后往前第一个递减的值。
### 关键点解析
* 写几个例子通常会帮助理解问题的规律
* 在有序数组中首尾指针不断交换位置即可实现 reverse
* 找到从右边起`第一个大于nums[i]的`，并将其和 nums\[i]进行交换
### 代码
语言支持: Javascript, Python3, CPP
JavaScript Code:
```js
/*
* @lc app=leetcode id=31 lang=javascript
*
* [31] Next Permutation
*/
function reverseRange(A, i, j) {
while (i < j) {
const temp = A[i];
A[i] = A[j];
A[j] = temp;
i++;
j--;
}
}
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var nextPermutation = function (nums) {
// 时间复杂度O(n) 空间复杂度O(1)
if (nums == null || nums.length <= 1) return;
let i = nums.length - 2;
// 从后往前找到第一个降序的,相当于找到了我们的回溯点
while (i > -1 && nums[i + 1] <= nums[i]) i--;
// 如果找了就swap
if (i > -1) {
let j = nums.length - 1;
// 找到从右边起第一个大于nums[i]的，并将其和nums[i]进行交换
// 因为如果交换的数字比nums[i]还要小肯定不符合题意
while (nums[j] <= nums[i]) j--;
const temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
// 最后我们只需要将剩下的元素从左到右，依次填入当前最小的元素就可以保证是大于当前排列的最小值了
// [i + 1, A.length -1]的元素进行反转
reverseRange(nums, i + 1, nums.length - 1);
};
```
Python3 Code:
```python
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
j = len(nums) - 1
while j >= 0 and nums[i] >= nums[j]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
left, right = i + 1, len(nums) - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
```
CPP Code:
```cpp
class Solution {
public:
void nextPermutation(vector& nums) {
int i = nums.size() - 2, j = nums.size() - 1;
while (i >= 0 && nums[i] >= nums[i + 1]) --i;
if (i >= 0) {
while (j > i && nums[j] <= nums[i]) --j;
swap(nums[i], nums[j]);
}
reverse(nums.begin() + i + 1, nums.end());
}
};
```
### 相关题目
* [46.next-permutation](https://github.com/azl397985856/leetcode/blob/master/problems/46.next-permutation.md)
* [47.permutations-ii](/leetcode-solution/medium/47.permutations-ii.md)
* [60.permutation-sequence](/leetcode-solution/medium/60.permutation-sequence.md)(TODO)
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/31.next-permutation.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.