下一个排列

题目：

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。整数数组的下一个排列是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。给你一个整数数组 nums ，找出 nums 的下一个排列。

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

示例 1：

输入：nums = [1,2,3]
输出：[1,3,2]

示例 2：

输入：nums = [3,2,1]
输出：[1,2,3]

示例 3：

输入：nums = [1,1,5]
输出：[1,5,1]

思路：

题目的意思是：有一个由number 组成的数组，把整个数组当成一个数字(initNum)，元素位置随意互换可以得到很多个数字，这些数组中，有的大于刚开始给定的数字，有的小于刚开始给定的数字，题目要寻找符合下面条件的一个数字（resultNums）：

该数字大于给定数字，并且在的所有大于 initNum 数字中，是最小的。

首先倒叙循环数组，找到第一个大于它后面元素的位置，获取到下标 index
- 即第一个：sums[index] < sums[index - 1]
如果没找到，那说明 nums 本身已经是最大的数字，则将整个数组从小到大排序即可。
如果找到了，
- 1、则需要将 index - 1 位置的元素换到后面去，换到与 nums[index - 1] 最接近，且大于 num[index - 1 ] 的位置。
- 2、并且nums 数组中，从 index 下标开始，后面的元素需要升序排列，这样保证较大的数字在后面。
- 由于上面两步，谁先谁后不影响结果，先排序再换位置，代码比较好理解。

代码：

const nextPermutation = (nums) => {
  if (nums.length <= 1) return nums;
        let index = 0;
        for (let i = nums.length - 1; i > 0; i--) { //寻找第一个符合条件的 index: sums[index] < sums[index - 1]
            if (nums[i] > nums[i - 1]) {
                index = i;
                break;
            }
        }
        if (index === 0) { // 如果 index === 0， 说明原来的数组是最大的数字
            return nums.sort((a, b) => a - b); // 直接从小到大排序即可
        }
 
        for (let i = index; i < nums.length; i++) { // 将 index 开始后面的数字升序排列
            for (let j = index; j < nums.length; j++) {
                if (nums[j] > nums[j + 1]) {
                    [nums[j + 1], nums[j]] = [nums[j], nums[j + 1]]
                }
            }
        }
 
        for (let i = index; i < nums.length; i++) { // 找出 index 及其后面的数字中，最小的，且大于 nums[index -1] 的元素，将其于 nums[index -1] 互换位置
            if (nums[i] > nums[index - 1]) {
                [nums[index - 1], nums[i]] = [nums[i], nums[index - 1]]
                break;
            }
        }
        return nums
}