力扣 31. 下一个排列

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

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

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

解析：

找到输入数组字典序中的下一个位置，感觉像是找规律一样..... （可以多举几个例子，找一下其中的共同点） 比如1，2，3，4，5的下一个字典序为1，2，3，5，4 可以看到只改变了最后两个数字，因为整个序列都是升序的

再比如1，5，4，3，2的下一个字典序为2，5，4，3，1 可以看到5，4，3，2是降序的，就需要找到比1的大的最小数字2，和1交换位置，然后后面的升序排序

于是，从中总结出规律，需要先找到左右两个下标left和right，left表示最后一组的升序数字的第1个，right表示left后面的数字中比l大的最靠右的数字，比如
1，2，3，4，5 -> left = 4 , right = 5
1，5，4，3，2 -> left = 1 , right= 2
然后，将left和right位置的数字交换，交换后，对left后面部分的数字进行升序排序即可

Java:

class Solution {
    public void nextPermutation(int[] nums) {
        int left = 0, right = nums.length - 1;
        for(int i = 0; i < nums.length - 1; i++) {
            if(nums[i] < nums[i + 1]) {
                left = i;
            }
        }
        for(int i = left + 1; i < nums.length; i++) {
            if(nums[i] > nums[left]) {
                right = i;
            }
        }
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        Arrays.sort(nums, left + 1, nums.length);
        return;
    }
}

JavaScript:

var nextPermutation = function(nums) {
    let left = 0, right = nums.length - 1;
    for(let i = 0; i < nums.length - 1; i++) {
        if(nums[i] < nums[i + 1]) {
            left = i;
        }
    }
    for(let i = 0; i < nums.length; i++) {
        if(nums[i] > nums[left]) {
            right = i;
        }
    }
    let temp = nums[left];
    nums[left] = nums[right];
    nums[right] = temp;
    let arr = nums.slice(left+1);
    arr.sort((a,b) => a - b);
    nums.splice(left+1,nums.length - left, ...arr);
    return;
};