这是我参与更文挑战的第28天，活动详情查看：更文挑战

前言

力扣第三十一题 下一个排列 如下所示：

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

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

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

示例 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]

一、思路

注意：更大的排列指的是数组内容不变且刚好比当前排列大，中间不能出现其它的排列。例如 123 的下一个排列是 132 而不是 321

在思路讲解前先思考一个问题 {2, 3, 4, 5, 2, 6, 5, 4, 3} 的下一个更大的排列是多少？

答案是：{2, 3, 4, 5, 3, 2, 4, 5, 6}

怎么做的呢？其实很简单，有以下两个原则：

尽可能使用小的低位替换靠右的高位（低位值 > 高位值）
替换结束后，从替换的高位向右升序排列（让大的值靠右）

举个例子

这里还是以 nums = {2, 3, 4, 5, 2, 6, 5, 4, 3} 作为例子来解释上面的两个原则

尽可能替换靠右的高位很好理解，因为越靠右值越小。6, 5, 4, 3 都是大于 2 的，那选择哪一个低位呢？当然是选择 3 了，这样就可以使之前 2 在的高位变化幅度最小。
第一步已经将 nums 修改为 nums = {2, 3, 4, 5, 3, 6, 5, 4, 2} 了。你会发现从替换后的 3 靠右的 6, 5, 4, 2 是将大的值放在高位的，所以需要使用升序将小的值放在高位。将替换后的 3 靠右的排列改为 2, 4, 5, 6
返回结果 nums = {2, 3, 4, 5, 3, 2, 4, 5, 6} 即可

二、实现

实现代码

一些说明：实现方式和思路中保持一致，先找到可替换的高位，然后交换元素，最后使用升序排列交换位置后的元素即可

    public void nextPermutation(int[] nums) {
        // 第一个元素表示最小可以替换的高位
        int[] place = new int[] {Integer.MIN_VALUE, 0};
        // 找到所有从右往左可以替换的位置
        for (int i=nums.length-1; i>0; i--) {
            // j为高位
            for (int j=i-1; j>-1; j--) {
                // 尽可能替换靠右的高位
                if (nums[i] > nums[j] && j>place[0]) {
                    place[0] = j;
                    place[1] = i;
                }
            }
        }
        int begin =0;
        // 如没有交换
        if (place[0] <= Integer.MIN_VALUE) {
            place[0] = 0;
        } else {
            // 交换i j
            int temp = nums[place[0]];
            nums[place[0]] = nums[place[1]];
            nums[place[1]] = temp;
            // 如交换过元素
            begin = place[0] + 1;
        }

        // 冒泡排序，i～j升序
        for (int i=begin; i<nums.length; i++) {
            for (int j=i+1; j<nums.length; j++) {
                if (nums[i] > nums[j]) {
                    // 交换i j
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }

            }
        }
    }
复制代码

测试代码

    public static void main(String[] args) {
        int[] nums = {2, 3, 4, 5, 2, 6, 5, 4, 3};
        new Number31().nextPermutation(nums);
        System.out.println(nums);
    }
复制代码