0031. Next Permutation.md

Explanation

Input: nums = [1,2,3] Output: [1,3,2]

• Traverse backward, 2 is the point that starts decreasing, and 3 is larger than 2, so swap 2 and 3

Input: nums = [3,2,1] Output: [1,2,3]

• sorted in ascending order

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */

/*
1st:
            i < i + 1
    1       2       3
    
- call next large i = 1
2nd:
                    this index > i, so return this, and swap
    1       2       3
    
    
*/
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function(nums) {
    for(let i = nums.length - 1; i >= 0; i--) {
        if(nums[i] < nums[i + 1]) {
            let large = nextLarge(i);
            swap(i, large);
            reverse(i + 1);
            return;
        }
    }
    nums.reverse();
    
    function nextLarge(index) {
        for(let i = nums.length - 1; i >= 0; i--) {
            if(nums[i] > nums[index]) {
                return i;
            }
        }
    }
    
    function swap(i, j) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    
    function reverse(index) {
        let i = index, j = nums.length - 1;
        while(i < j) {
            swap(i, j);
            i++;
            j--;
        }
    }
};