题目

LeetCode.31.下一个排列（中等）

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

题解

字典序是什么意思？

顾名思义，就跟字典里的单词排布顺序一样。

字典序中下一个排列是什么意思？

只能查定义，然后举几个例子：

每一个排列都是从小到大递增的。

总结下一个排列的大致规律：

数字要变大
变大的幅度要最小

具体怎么获取下一个排列，可以一步步推理分析。

怎么增大一个普通的数？

把某一位的数字变大。

如何保证一个普通的数增大的幅度最小？

在最低位做加法。
加最小的数字1。

增大给定的数字序列可以跟增大一个普通数字一样吗？

不一样。

因为要找下一个排列，数字还是序列中的那些数，数字不能随便用，只能用给定的数字序列里的数字。

那怎么增大给定的数字序列？

确定一个要变大的位，假设这一位数字为x。
再找一个比x的大的位，两个位的数字做交换，保证不使用额外数字。

同时要变大的位尽可能是低位，才能保证增幅最小。

具体需要怎样的条件，交换数字位后才能获得更大的数字序列？

某两位交换，一个是高位，一个是低位。

如果 高位数字 >= 低位数字，交换过后，整个数变得更小了。
只有在 高位数字 < 低位数字时做交换，整个数才会变得更大。

应该选取哪个低位数字和哪个高位数字做交换？

刚才的分析明确了两个条件：

要从低位往高位找数字位。
高位数字 < 低位数字。

也就是说，如果低位有一个非递增序列（递减或相等序列），可以确定要找的高位数字肯定不在这个非递增序列里的，否则交换后无法变得更大。

那要找的高位数字在哪？

一定是处在一个递增序列中，且位数尽可能低。

也就是从右到左发现的第一个递增序列中第二大的数。

比如[1, 2, 3, 8, 6, 1]，我们要找到的高位数字是3。

为什么不能是8？

因为8要是高位，低位只能在8的右边找一个数，这两个是递减的，交换后不会让整体更大。
如果3是要找的高位，至少可以跟比3大的8互换，整体可以形成更大的数，并且3是最低的符合条件的位了。

换成代码表达：
从右到左遍历num数组，一旦第一次发现num[i - 1] < num[i]，num[i - 1]就是要找到的高位数字。

要找的低位数字在哪？

现在有3个已知条件：

要从低位往高位找。
高位数字 < 低位数字。
高位数字位置已确定。

高位数字位置已确定，低位数字位置的范围也就确定了，肯定在末尾的非递增序列里。

那么就从右到左遍历，寻找第一个大于高位数字的数就是要找的低位数字了。

为什么要寻找第一个大于高位数字的数？

假设：

第一个大于高位数字的数去做交换后，得到的整个数变为a。
第二个大于高位数字的数去做交换后，得到的整个数变为b。

可以发现b > a，a是更大的数中增幅较小的那个，b不满足题目要求。

交换后得到的新数字是下一个排列吗？

回到最开始的例子，带入观察。

以1 2 3 5 4为例，要找的高位是3、低位是4，交换后得到1 2 4 5 3，但不是下一个排列，下一个排列是是1 2 4 3 5。
两者区别在于，交换后低位的5 3变成了3 5才算是更小的排列。

交换后怎么得到下一个排列？

把末尾递减序列变成递增序列，就是更大的排列中最小的那个排列，也就是下一个排列。

算法步骤

四步走：

从右到左寻找第一个递增序列，确定高位x。
从右到左寻找第一个大于x的低位y。
交换x和y。
把高位右边的递减序列从小到大排序。

边界处理

如果序列完全递减，找不到递增序列，要做边界判断。

如何高效的排序递减序列？

这里可以不需要排序算法，递减序列变递增序列只需要用双指针不停的首尾交换就行了，这样只需要O(n)时间，避免了排序的O(n * log n)。

复杂度

时间复杂度O(n)：n为序列长度，寻找递增序列、寻找低位、递增变递减最多遍历完整个序列，都是O(n)时间，线性叠加还是O(n)。
空间复杂度O(1)。

class Solution {
    fun nextPermutation(nums: IntArray): Unit {
        val n = nums.size

        // 寻找要变大的位
        var i = n - 2
        // 末尾是递减序列（或相等）就跳过，直到发现递增序列
        while (i >= 0 && nums[i] >= nums[i + 1]) i--
        
        // 此时若i == -1，说明序列全部递减
        // 若i >= 1，说明发现了递增序列

        // 通过交换把数字序列变大，且增幅最小
        if (i >= 0) {
            // 从末尾递减序列中从右向左找到第一个大于nums[i]的数
            var k = n - 1
            while (nums[i] >= nums[k]) k--

            // 交换后，变成更大的数，增幅最小
            nums.swap(i, k)
        }

        // 末尾递减序列变成递增序列，使得整体序列最小
        var start = i + 1
        var end = n - 1
        while (start < end) {
            nums.swap(start, end)
            start++
            end--
        }
    }

    private fun IntArray.swap(i: Int, j: Int) {
        val nums = this
        val tmp = nums[i]
        nums[i] = nums[j]
        nums[j] = tmp
    }
}