文章目录

1. 1. Next Permutation

Next Permutation

---

这道题目主要利用对数组的操作来实现。

比如

2 1 3 1 6 4 下一个的排列是 2 1 3 4 1 6；

可以从后面来观察数列，6 4构成了一个向上的坡度（从后向前看），到1的时候下去了，那么在1 4 6中第二小的是4,新的数列得以4开头，其他按顺序排列。那么只要交换1和最后一个元素，然后对波峰到结尾的数进行逆序即可。

只需要交换刚下落的这个数和结尾的数就可以了吗？

我们再来看一个列子，再比如

1 2 3 6 4 1 下一个的排列是 1 2 4 1 3 6；

如果我们按上面的规则交换的话，就变成了1 2 1 3 4 6，但是这个顺序是比原来的要前面的。

所以我们的方法不能简单的挪动最后一个，需要在那个上升趋势的数列中找到第一个比下降数大的数。

算法整体思路：

1. 从最后一个元素开始，往前遍历，找到第一个下降的数low；
2. 再从最后一个元素开始，找到第一个比low大的数bigger;
3. 交换bigger和low；
4. 将最后一个元素到波峰的顺序数组逆序。