31.下一个排列

题目

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

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

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

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

方法

当给定排列已经是最大排列时，这种情况单独考虑，只需反转数组即可。

否则，下一个排列肯定比当前排列要大，而且要尽可能让变大的幅度很小。

步骤如下：

1. 从后向前遍历数组，找到第一个升序位置对 (index,index+1)，满足 a[index] < a[index+1]。在index之后的所有位置i，都符合降序。意味着nums[index…]为以index开头的最大排列。既然我们要找一个更大的排列，意味着不能再以index开头，我们要在index位置后面找到一个最小比它大的数代替它。
2. 于是我们在index位置右边从后向前寻找第一个比nums[index]大的元素位置j。因为nums[index+1….]为降序排列，因此第一个出现的比nums[index]大的元素就是最小比nums[index]大的元素。
3. 之前nums[index…]为以nums[index]开头的最大排列，现在我们要让nums[index…]变为以nums[j]开头的最小排列，于是将index位置和j位置交换，即让一个最小的比nums[index]大的元素nums[j]代替它。
4. 再反转nums[index+1…..]，让这段区间由降序变成升序。此刻index位置右边为以nums[j]元素开头的最小排列。

public void nextPermutation(int[] nums) {
    int index = nums.length - 2;
    //1.寻找第一个升序位置对
    while(index >= 0 && nums[index] >= nums[index + 1])
        index--;
    //如果没找到一个升序位置对，则整个数组为降序，即最大排列，这时将其反转得到最小排列
    if(index < 0)
        reverse(nums, 0, nums.length - 1);
    //否则，(index,index+1)为找到的第一个升序位置对
    else{
        //2.在index右侧寻找最小的比nums[index]大的位置j
        int j = nums.length - 1;
        while (j >= 0 && nums[index] >= nums[j]) 
            j--;
        //3.将位置i和位置index上的元素交换
        swap(nums, index, j);
        //4.反转index右边，使得其由降序变为升序
        reverse(nums, index + 1, nums.length - 1);
    }
}

public void swap(int[] nums, int a, int b){
    int temp = nums[a];
    nums[a] = nums[b];
    nums[b] = temp;
}
//将数组arr逆序
public void reverse(int[] nums, int start, int end){
    if(end - start < 1)
        return;
    int left = start;
    int right = end;
    while(left < right){
        swap(nums, left++, right--);
    }
}

• 时间复杂度：O(N)
• 空间复杂度：O(1)