下一个排列

原题链接

解题思路

根据题意，可以进行如下操作，达到效果。

1. 从数组的尾向前查找一个“较小值”，找到两个相邻的数，且为升序排列，则靠前的那个数即为“较小数”。
2. 从较小数的下一位开始，一直到数组尾部，找“较大数”，要求：较大数不能太大，即比“较小数”略大一点即可。
3. 接下来交换“较大数”和“较小数”，然后将原来“较小数”位置以后的剩余数进行升序排列，就可以达到题目要求。
4. 如果第一步就没找到较小值，说明整个数都是降序排列的，直接说明当前的数就是全排列中最大的数，所以直接将数组升序排列返回即可。

import java.util.*;

public class Solution {
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length == 1) {
            return;
        }
        int i = nums.length - 1;
        // 先倒着找“较小数”，接下来从“较小数”开始往后找“较大数”
        while (i > 0) {
            // 找较小数，满足升序，则靠前的那个数(i - 1)即为所找“较小数”
            if (nums[i] > nums[i - 1]) {
                // 如果找到了，则开始找“较大数”
                int min = nums[i];
                int k = i;  // k从i位置开始，向后找“较大数”,起到标记作用
                for (int j = i; j < nums.length; j++) {
                    if (nums[j] < min && nums[j] > nums[i - 1]) {
                        min = nums[j];
                        k = j;
                    }
                }
                swap(nums, i - 1, k);
                Arrays.sort(nums, i, nums.length);  // 较大数与较小数交换位置之后，[i, length - 1]正序排序
                break;
            }
            i--;    // 没找到，i继续向后查找
        }
        if (i == 0) {
            // 没找到较小数，当前的数就是全排列结果中的最大数，
            // 所以直接正序排列，得到最小的数，从头开始
            Arrays.sort(nums);
        }
    }

    /**
     * 交换数组两数
     *
     * @param nums
     * @param i
     * @param j
     */
    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /**
     * 数组反转
     *
     * @param nums  数组
     * @param start 从start位置之后开始反转
     */
    public static void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    /*public static void main(String[] args) {
        int[] nums = {1, 1, 5};
        new Main().nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }*/
}