Next Permutation

Difficulty: Medium

这道题其实如果能想明白怎么做的话，还是很简单的。。。

简单地说，想要获得给定数组$a$的下一个排列，也就是要找到字典序在$a$之后的最靠前的那个排列。那么直观的来讲，调整的位置肯定要尽可能的靠后一些。

那么到底要多靠后呢？

假设序列$a[i:] = a[i, i+1, \cdots, n-1]$是递减的，那么$a[i:]$的字典序就已经达到了最大，调整的范围应该进一步扩大，直到找到某一个$i’$，$a[i’]<a[i’+1]$. 这时候就可以断定，只要能得到$a[i’:]$这个序列的下一个排列，将其与$a[:i’]$部分拼接起来，就可以得到$a$的下一个排列了。

当我们已经确定了需要调整的范围以后，怎么进行调整呢？

我们现在已经找到了$i$满足$a[i]<a[i+1]$，并且$a[i+1:]$是降序的。这就说明，在以$a[i]$为起始元素的前提下，这个序列的字典序无法进一步提高了。因此，我们需要在$a[i+1:]$这个序列里面找到一个大于$a[i]$的最小的元素$a[j]$，以$a[j]$作为新的起始元素。

之所以选择大于$a[i]$的最小元素，是因为一方面只有大于$a[i]$才能保证字典序增大，另一方面大于$a[i]$的最小元素，可以使得字典序的增量较小。

将$a[j]$作为新的起始元素后，字典序确实变大了，但是增加的太多了。我们需要找到一个以$a[j]$作为起始元素的字典序最小的一个排列。那么只需要将$a[i:]$这个序列中除了$a[j]$以外的其他所有元素按照升序填入$a[j]$之后即可。

这样的算法经过一些简单的优化以后就可以达到$O(n)$的复杂度了。