31. 下一个排列

描述

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。

示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]
示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]
示例 4：
输入：nums = [1]
输出：[1]

code

class Solution {
    public void nextPermutation(int[] nums) {
        if(nums == null || nums.length == 1) {
            return;
        }

        // 从后往前找
        int i = nums.length - 1;
        while(i > 0) {
            // 找到一个比后面数字小的
            if(nums[i] > nums[i - 1]) {
                // 后面数字的最小值
                int min = nums[i];
                int k = i;
                for(int j = i+1; j < nums.length; j++) {
                    // 该最小值要比nums[i-1]大，这样才可以交换
                    if(nums[j] < min && nums[j] > nums[i-1]) {
                        min = nums[j];
                        // 标记最小值的位置，以便交换
                        k = j;
                    }
                }
                exch(nums, i - 1, k);
                // 对交换后,i-1之后的数组排序
                Arrays.sort(nums, i, nums.length);
                break;
            }
            i--;
        }

        // 降序数组直接重排
        if(i == 0) {
            Arrays.sort(nums);
        }
    }

    private void exch(int[] nums, int i, int k) {
        int tmp = nums[i];
        nums[i] = nums[k];
        nums[k] = tmp;
    }
}