下一个排列

31. 下一个排列

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

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

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

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

下一个排列总是比当前排列要大，除非当前排列是最大的，我们需要找到一个下一个排列，且变化的幅度尽量小。

我们需要找到一个尽量靠右的较小数和尽量小的较大数，交换这两个数使排列变大，同时交换之后我们需要将较小数右边的递减序列重排，来得到变换幅度最小的序列。

以[1, 5, 8, 4, 7, 6, 5, 3, 1]为例，我们可以得到下一个序列[1, 5, 8, 5, 1, 3, 4, 6, 7]。

直观的想法是，从右至左找到第一个不是递减序列中的值，找到了 4，它右边的递减序列为 [7, 6, 5, 3, 1]。接下来找一个数和 4 交换，这个数必须比 4 大（比 4 小的序列已经生成过）又要使变化幅度最小，我们找到了第一个大于 4 的数 5。将 4 和 5 交换，得到[1, 5, 8, 5, 7, 6, 4, 3, 1]，还需要将 5 右边的递减序列翻转，得到[1, 5, 8, 5, 1, 3, 4, 6, 7]。

class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        //从右至左找到一个不是递减序列中的值
        while(i >= 0 && nums[i] >= nums[i + 1]){
            --i;
        }

        if(i >= 0){
            //在递减序列中找到一个比前一个找到的值稍大的数
            int j = nums.length - 1;
            while(j >= 0 && nums[i] >= nums[j]){
                --j;
            }
            //交换这两个数
            swap(nums, i, j);
        }
        //将右边的递减序列翻转
        reverse(nums, i + 1, nums.length - 1);
    }

    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void reverse(int[] nums, int start, int end){
        int left = start, right = end;
        while(left < right){
            swap(nums, left, right);
            ++left;
            --right;
        }
    }
}

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