> For the complete documentation index, see [llms.txt](https://851958789.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://851958789.gitbook.io/notes/0031_next_permutation/slt.md).

# 思路1

首先我们搞清楚什么是next permutation。1、2、3的全排列：

```
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
```

可见next permutation就是全排列顺序中的下一个。

再来看一个长一点的例子。有如下的一个数组

```
1　　2　　7　　4　　3　　1
```

下一个排列为：

```
1　　3　　1　　2　　4　　7
```

观察可以发现，再给出的数组中，2之后的数字都是降序排列的，我们把2后面第一个比2大的数字（这里是3）和2交换，然后让3后面的数字升序排列。

交换和逆序两步的顺序不重要

先交换，再逆序：

127431 137421 131247

先逆序，再交换

127431 121347 131247

简单思路的证明：从7开始是降序的，也就是说7 4 3 1不可能通过重新排列构成更大的数字。如果要得到next permutation，那么必须把2这个位置的数字给换掉才行，而且只能换成比2大的数字在才能使next permutation > current permutation.至于换成多大的数字，很明显的需要换成在2后面的数字中刚好比2大的数字。

注意 找兩個索引：最大元素 和 從右往左第一個比 最大元素前一個元素大的元素 两次遍历都是从后往前哦。