leetcode-31. 下一个排列

JAVA解法

class Solution {
    public void nextPermutation(int[] nums) {
        // 将 i 的位置定位到倒数第二个位置,因为下方有 i + 1
        int i = nums.length - 2;
        // 找到数字排列从左往右非降序时的转折点(断点第一个)
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        // 只有 i 大于等于 0 才能进行下一步操作
        if (i >= 0) {
            // 将 j 的位置定位到倒数第一个位置
            int j = nums.length - 1;
            // 遍小开始遍历数字排列并一一与第一个不符合降序的值即转折点对比
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            // 直到转折点的值小于从右往左遍历到的第一个值即进行交换
            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) {
        // 定义左边位置为传进来的 start,右边位置为数字排列的最后一个值
        int left = start, right = nums.length - 1;
        // 只要 left 位置小于 right 的位置就进行交换
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}

题解分析

这道题非常有趣，好像在玩游戏，首先得理解好这道题的意图。下一个排列，我们可以理解为数字排列的下一个值，即大一点但无固定的尺度，即使用已有的数字排列。

首先从右到左的连续升序子序列存在一个转折点，我们只需要让这个转折点的值大一点，怎么衡量这个一点就从从右到左的连续升序子序列中寻找一个刚好比这个转折点大的数，并与之交换，此时再把这个连续升序子序列进行反转即可得到连续降序子序列，因此整个操作只让转折点大一点，而后边的连续序列则从最大的排序序列变为最小排序序列，最终达到题目要求。

leetcode原题：31. 下一个排列