Leetcode 31 Next Permutation 题解分析

这题的题目介绍有一定的误导性，没有把字典序说明白，虽然的确是常规意义的字典序，但是题目介绍给的序列顺序反而会让人觉得那样不对
这里我们逐步深入地来讲这个题，也类似于找规律
注意：这里的递减递增序列都是从前往后看的
字典序可以就当查字典，或者默认的字符串排序方式，就是对于一个序列，逐个字符对比，同一位的相同再对比下一位的，例如 11在12前面，12在13前面，
那对于同一组字符或者像题中的数字，以最简单的12来分析，因为这个就两种排列，12跟21，按字典序排列，12在前，21在后
通过这个仔细点也能发现，或者再举个例子123，这个排列就会多一些了

1
2
3
4
5
6

123
132
213
231
312
321

一共有这么几种，不过举这个例子是为了更具体的发现规律，对于第一个数字相同的情况，比如123跟132，是132在后，发现规律没，递增序列是最小的，递减序列是最大的，因为2个数字 只有两种排列，扩展到3个数字，也可以把它拆分开，同样是第一个数字是1，后面两个数字就又回到了前面12序列的情况，
所以就可以把问题分成两部分来解决，首先从后往前找到递减序列
通过例子来讲

1

1 4 6 5 3 2

为什么要找到递减序列，因为递减序列已经是最大的了，要做调整要在这个之前调整，并且要找的是下一个序列，所以要是最接近的那个，否则我找到的可能就是下N个了，这个有点类似于数学里进位的意思，比如十九，九已经是个位里最大的了，找下一个比它大的只能是前面一位加一，但是加一以后需要九变到这一位的最小，也就是零。
对于上面的例子，递减序列就是6532，第一个非递减的是4，我要找下一个就是要比当前这个大，那我就去后面找比4大的，至于为什么能找到，因为这是递减序列边界之外的，说明肯定有比它大的，那要找哪个呢，要找比4大的数字里最小的，这样才是最近的下一个序列，并且因为后面是递减序列，所以可以直接从后往前找第一个
也就是会找到 5
找到 5 之后就做交换

1

1 5 6 4 3 2

这样是不是就行了呢，不行，因为这不是下一个，而是下N个，当4变成5之后，这个序列不管5后面的数字怎么变都是比 146532 大的，但是要找的是下一个，最接近的那个，则需要后面的序列变成最小，也就是变成递增序列，也就是

1

1 5 2 3 4 6

这里有两种例外情况，或者严格来说是一种
第一种是本身整个就是递减序列了，这在题中说了，下一个就是从头再开始，那就也很简单整个排序成递增的就行了
第二种是本身就是个完全递增的，那其实就交换末两位，但这种跟上面的可以糅合在一起，比如就是

1

1 2 3 4 5 6

单个6构不成递增或递减，找到的第一个非递减的数字就是 5 ，那就是在 5 后面找一个比它大的做交换，这时只有 6 ，所以就 5 跟 6 交换下，然后单个 5 做排序也等于不用做
再结合代码来看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public void nextPermutation(int[] nums) {
        int n = nums.length, i = n - 2, j = n - 1;
        // 这个while循环是为了从后往前找到递减序列的分界点
        // 循环完成后i就是递减序列左边的第一个数字位置
        while (i >= 0 && nums[i] >= nums[i + 1]) --i;
        if (i >= 0) {
            // 表示有找到分界点，然后就从后往前找到第一个比nums[i]大的做交换
            while (nums[j] <= nums[i]) --j;
            // 这个while循环在找到第一个nums[j] > nums[i]时退出
            // 下面就是做交换
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        // 因为前面已经保证了逆序，这里只要排成正序就是最小的了
        Arrays.sort(nums, i+1, nums.length);
    }