刷一道有意思的算法题 LC31

题目链接：31. 下一个排列

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

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

示例 1：

输入：nums = [1,2,3]
输出：[1,3,2]

示例 2：

输入：nums = [3,2,1]
输出：[1,2,3]

示例 3：

输入：nums = [1,1,5]
输出：[1,5,1]

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 100

思路

「下一个排列」的定义是：给定数字序列的字典序中下一个更大的排列，如果不存在下一个更大的排列，将数字序列重新排列成最小的排列（升序排列）。

问题转换：给定若干个数字，将其组合为一个整数，如何将这些数字重新排列，以得到下一个更大的整数。

「下一个」要求：数字更大、增幅尽量小。

【🌰栗子】以 1, 2, 3, 4, 5, 6 举例，排列依次是：123456 < 123465 < 123546 < ... < 654321。

那么如何得到这样的排列呢？

「下一个数」> 「当前数」 => 需要将后面的「较大数」和前面的「较小数」交换；
增幅尽量小：
1. 尽可能在靠右的地位上寻找合适的数字，倒序遍历；
2. 将一个尽可能小的「较大数」和前面的「较小数」交换；比如 123465，下一个排列应该交换 4 和 5；
3. 将「较大数」交换到前面之后，还需要做的是将「较大数」后面的元素排列做升序处理，升序排列就是最小的排列。

过程：123465 -> 123564 -> 123546。

算法实现思路：

从后向前查找第一个相邻升序的元素对 (i,j)，nums[i] < nums[j] => 此时 [j, n-1] 是降序；
在 [j, n-1] 从后向前查找第一个满足 nums[i] < nums[k] 的下标 k，交换 nums[i] 和 nums[k]；
[i+1, n-1] 做升序处理；
如果步骤 1 找不到符合的相邻的元素对，说明当前 [0, n-1] 是一个降序序列，直接跳到步骤 3 做升序处理。

实现

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        if(n <= 1) return ;

        int mn = -1; // 相邻升序对中的较小值
        for(int i = n - 2; i >= 0; i--) {
            if(nums[i] < nums[i + 1]) {
                mn = i;
                break;
            }
        }

        if(mn != -1) {
            // [mn+1, n-1] 是降序
            // 倒序遍历，找到一个 >nums[mn] 的值，与 nums[mn] 交换
            for(int i = n - 1; i > mn; i--) {
                if(nums[i] > nums[mn]) {
                    swap(nums, i, mn);
                    break;
                }
            }
        }

        // [mn+1, n-1] 是倒序，做升序处理，让增幅尽量小
        for(int i = mn+1, j = n-1; i < j; i++, j--) {
            swap(nums, i, j);
        }
    }

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

class Solution {
    public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return;

        int mn = -1; // 相邻升序对中的较小值
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                mn = i;
                break;
            }
        }

        if (mn != -1) {
            // [mn+1, n-1] 是降序
            // 倒序遍历，找到一个 >nums[mn] 的值，与 nums[mn] 交换
            for (int i = n - 1; i > mn; i--) {
                if (nums[i] > nums[mn]) {
                    swap(nums[i], nums[mn]);
                    break;
                }
            }
        }

        // [mn+1, n-1] 是倒序，做升序处理，让增幅尽量小
        for (int i = mn + 1, j = n - 1; i < j; i++, j--) {
            swap(nums[i], nums[j]);
        }
    }
};

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        if n <= 1: return

        mn = -1
        for i in range(n - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                mn = i
                break
        
        if mn != -1:
            for i in range(n - 1, mn - 1, -1):
                if nums[i] > nums[mn]:
                    nums[i], nums[mn] = nums[mn], nums[i]
                    break
        
        i, j = mn + 1, n - 1
        while i < j:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1

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