【31】下一个排列：中等

https://leetcode-cn.com/problems/next-permutation/ 数组

基础

这也是官方的方法，这样做性能不是很好，可以加强

/**
 Do not return anything, modify nums in-place instead.
 */
function nextPermutation(nums: number[]): void {
    let i = nums.length - 2;
    while (i >= 0 && nums[i + 1] <= nums[i]) {
        i--;
    }
    if (i >= 0) {
        let j = nums.length - 1;
        while(j >= 0 && nums[j] <= nums[i]) {
            j--;
        }
        [nums[i], nums[j]] = [nums[j], nums[i]]
    }
    reserve(nums, i + 1)
};
function reserve(nums: number[], start: number) {
    let i = start;
    let j = nums.length - 1;
    while(i < j) {
        [nums[i], nums[j]] = [nums[j], nums[i]]
        i++;
        j--;
    }
}

进阶

解题思路，只要前面的有一个比后面的小了，那就可以从后面找一个最小的，放到当前位置，然后后面的内容做从小到大的排序

/**
 Do not return anything, modify nums in-place instead.
 */
function nextPermutation(nums: number[]): void {
    let i = nums.length - 1;
    for (; i > 0; i--) {
        if (nums[i] > nums[i - 1]) {
            break;
        }
    }
    let minIndex = i;
    for (let j = i; j < nums.length; j++) {
        if (nums[j] > nums[i - 1] && nums[j] < nums[minIndex]) {
            minIndex = j;
        }
    }
    if (i > 0) {
        [nums[minIndex], nums[i - 1]] = [nums[i - 1], nums[minIndex]]
    }
    nums.splice(i, nums.length, ...nums.slice(i).sort((a, b) => a - b))
};