# 题目：下一个排列

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-permutation

# 解题思路

首先下一个排列代表当前序列后下一个更大的排列，而这个排列不能过大，以1,2,3,6,4,5,2,1为例子，它下一个排列是1,2,3,6,5,4,2,1，而不是1,2,4,1,2,3,5,6，可以这样分析：

• 既想让排列变得更大，但又符合刚好是下一个排列的要求，只需要从后面对数字进行交换，后面交换的位置越往后就越有可能成为下一个排列，还是以1,2,3,6,4,5,2,1=>1,2,3,6,5,4,2,1来看：
  • 1,2,3,6,4,5,2,1中5,2,1是一个倒序递增序列，这个序列已经是最大的了，而到4,5,2,1后就不一样了，后面还有一个5,4,2,1比它更大，4和5交换后就刚好满足下一个排列的要求，而这个5可以看成是交换的分界点，找出分界点逻辑是这样的：

let idx = nums.length - 1;   //分界点索引
while (nums[idx] <= nums[idx - 1]) idx--;    //确保分界点右边是一个倒序递增序列

• 划完分界点后是否就是分界点和分界点前一个数字交换呢，当然不是，比如1,2,3,6,5,4,2,1=>1,2,4,1,2,3,5,6,它的分界点是6，但实际上并没有把3和6互换，而是从6,5,4,2,1中找出4和3互换，而原因也很简单，在前面的条件中可以知道分界点及分界的右边是一个倒序递增序列，而这个序列至少有一个以上数字是比3大的，从序列倒序中找出第一个比3大的数字才能满足下一个排列的要求

let left = idx - 1,   // 分界点左边数字索引，也就是3的索引
    right = nums.length - 1;

while (nums[left] >= nums[right]) right--;  // 找出第一个比3大的数在哪

• 在把3和4交换后变成需要把4后面的序列变成降序，也就是1,2,4,6,5,3,2,1中6,5,3,2,1变成1,2,3,5,6，而这里只需要用双指针头尾开始循环互换即可。

# 代码实现

let nextPermutation = function (nums) {
    let idx = nums.length - 1;
    while (nums[idx] <= nums[idx - 1]) idx--;

    let left = idx - 1,
        right = nums.length - 1;

    while (nums[left] >= nums[right]) right--;

    if (left >= 0 && right >= 0) {
        [nums[left], nums[right]] = [nums[right], nums[left]]
    }

    left = idx;
    right = nums.length - 1;
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left++;
        right--;
    }
};