题目描述

https://leetcode.cn/problems/next-permutation/

解题思路

理解下一个排序的意思：

参照：https://leetcode.cn/problems/next-permutation/solution/xia-yi-ge-pai-lie-by-leetcode-solution/

我们从后向前寻找第一个降序的数字，此时后边的都是降序，保证了排序尽可能的小，所以，在从后先前找到第一个比他大的数字，此时交换，即可获得一个排列，但是不是最小的，因为后边还有部分降序，此时把后边的降序变为升序即是最小的排序。

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 >= i && nums[j] <= nums[i]) {
                j--;
            }
            // 交换2个位置
            swap(nums, i, j);
        }
        // 反转数组，后面已经是从大到小的，小的往前放
        reverse(nums, i + 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 = nums.length - 1;
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }
}