解决方案：下一个排列

这是 Leetcode 解题系列讲解（索引）的一部分。如果您喜欢这个解法或觉得它有用， 请点赞 此文和/或 在 Leetcode 论坛上为我的解法点赞 。

LeetCode 问题 #31（中等）：下一个排列

描述：

实现下一个排列，将数字重新排列为按字典顺序排列的下一个更大的数字排列。

如果无法进行这样的排列，则必须将其重新排列为尽可能低的顺序（即按升序排列）。

替换必须到位并且仅使用常量额外内存。

限制：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

主意：

对数组左侧部分的更改对字典序排序的影响比对右侧部分的更改更大，因此从逻辑上讲，为了找到字典序更大的下一个排列，我们需要找到最右边可以替换为更大数字的数字。此外，更大的数字必须来自目标数字的右侧，否则你会创建一个字典序更低的排列。

我们还需要确保它不是任意较大的数字，而是其右侧数字中下一个可能的较大数字。然后，我们需要确保交换目标右侧的剩余数字按字典顺序排列，且排列顺序最小。（可以将其想象成一个计数器，从0999滚动 到1000。）

执行：

所以第一步就是找到我们想要交换的目标数字。我们从右向左检查，如果每个数字都比前一个数字大，那么我们显然找不到字典序更大的数字。因此，我们必须向左移动，直到找到第一个比它右边的数字小的数字。

一旦我们找到目标（N[i]），需要注意的一点是，目标右侧的数字已经按顺序排列，只是顺序相反，因此我们可以轻松地反转它们。 （即使我们实际上没有找到目标，我们仍然希望按照说明反转整个数组。）

然后，我们很容易就能从反转后的数字中最小的移动到最大的，并找到第一个大于目标的数字 ( N[j] )，这样我们就可以交换这两个数字了。由于N[j]在字典顺序上与N[i]最近，因此即使交换后， N[i]右侧的子数组仍然保持正确的顺序。

用于交换数组元素的简单辅助函数将会很有用。

Javascript代码：

var nextPermutation = function(N) {
    const swap = (i, j) =>
        [N[i],N[j]] = [N[j],N[i]]

    let len = N.length - 1, i
    for (i = len - 1; N[i] >= N[i+1];) i--
    let j = i + 1, k = len
    while (j < k) swap(j++,k--)
    if (i >= 0) {
        for (j = i + 1; N[i] >= N[j];) j++
        swap(i,j)
    }
};