1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length < 2)
            return;
        int pos = nums.length - 2;
        while (pos >= 0 && nums[pos] >= nums[pos + 1]) {
            pos -= 1;
        }
        if (pos != -1) {
            int ptr = nums.length - 1;
            while (nums[ptr] <= nums[pos]) {
                ptr -= 1;
            }
            swap(nums, pos, ptr);
        }
        int left = pos + 1;
        int right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left += 1;
            right -= 1;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

想象成给你一列数字, 一共n个, 每个数字代表一位, 让你组合所有可能的长n位的数字. 这就是permutations啊. 从最小的组起. 也就是把给的数字sort后呈现出来的东西就是最小值, 然后每次往上增加一点, 看能组合成什么. 到最后所有的数字倒序排产生的东西就是最后一种permutation, 也就是能表达出来的最大的值.

假设我们组合到了某个数字, 那紧接着的permuation要比它大, 但是是比该数字大的permutations中最小的. 我们先假设前n - 1位不变, 剩余一位, 能不能组合一个更大的数字呢? 不行, 因为就只剩一位. 然后假设前n - 2位不变, 剩余两位数字, 如果此时个位比十位大就行. 如果没有, 那么我们假设前n - 3位不变. 剩下右边三位, 右边三位越靠左, 权重越大(百位, 十位, 个位). 我们知道十分位的数字大于个分位数字(只有这样才可能来到这种情况, 否则我们之前就找到next permutation了), 如果百分位的数字比十分位还要大, 那么这三位没办法再组成更大的数字. 因为这三位是倒序排列, 是能组合出来的最大的了. 同理我们一直假设, 会有这么一种情况, 在某处n, 它比它右边的数字中的某一位小, 它右边的数字都是弱递减(从左向右递减或者不变), 也就是说明n右边的数字组成了能够组成的最大的数字, 但是到了n这一位, 出现了比n右侧某个数字小的情况. 右侧这样的数字可能有多个. 那么我们如何保证让next增大的幅度最小呢? 现在是在n位及以前不变的情况下, 能组成的最大值, 那么我们就让第n位稍稍增加, 让右侧比第n位大的数字中最小的数字和第n位数字交换即可. 此时第n位的增幅最小, 不会让增加幅度太大. 那么如果右侧有多个这样的比第n位大, 但是是在比第n位大的数字中最小的这样的数字呢? 我们可以这么想, 当第n位和右边某个数字交换后, 我们接着需要把第n位右侧的数字sort一下(给定一串数字, 如何让它们组成的数字最小? 那肯定是从小到大排列). 这样我们能得到第n位稍微提升一点的情况下的最小值, 这个值比原先的值要大, 但又是比原先值要大的permutations中最小的, 因为此时第n位提升的最小, 且右侧数字组成的数字也最小.

那么我们如何优化这个sort呢? 我们已经知道交换前右侧数字是弱递减了. 那么现在我们如果能让交换后还保持这个弱递减的特性, 那直接reverse一下右侧的数字就sort好了. 于是我们自然而然想到让原先第n位和候选数字中最右边的那个交换. 该候选数字的左侧到第n位(不包含第n位)肯定是大于等于候选数字, 该候选数字右侧是小于该候选数字的(不可能等于否则右侧的数字才是最靠右的候选数字). 我们交换以后, 第n位出现在最右侧候选数字的位置, 此时的左侧不用说肯定是大于等于原先第n位数字(被交换的候选数字是大于等于第n位中最靠右的), 原先第n位数字的新位置的右侧是比第n位要小的, 否则侧某个数字才是应该被交换的最右侧的候选数字. 这样交换后, 这个弱递减性也保持住了, 我们直接reverse一下第n位右侧的数字即可.

有一种可能就是我们从右往左, 发现数字一直是弱递增, 此时, 给定的数字构成它们能表示的最大值, 我们就返回这些数字sort后的结果即可, 即wrap到这些数字能表达的最小值处, 能表达出的最大值的下一个permutation就是一开始能被表达的最小值.

给定一列数字, 能表达的最小值就是sort完后的样子, 因为肯定是让小的数字占据高位, 大的数字占据低位; 能表达的最大值就是反向sort后的样子, 同理要想让结果最大, 大的数字站在大的权重, 小的数字站在小的权重.

我们上面的过程就是去寻找后多少位构成了这些位上的数字能组成的最大, 但是后n + 1位却没有, 此时后n + 1能有更大的数字被组合出来, 表示有提升的空间. 我们就让n + 1位和它右侧数字中比n + 1位大的那些数字中的最靠右的那个数字交换, 然后n + 1位右侧数字reverse一下就可以了.

时间复杂度: O(n)
空间复杂度: O(1)