📃 题目描述

题目链接：31. 下一个排列 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

🔔 解题思路

这题感觉考的就是数学思维，反正我这种笨比不看答案是一个想法也蹦不出来（哭了）

我们希望下一个数比当前数大，这样才满足“下一个排列”的定义。⭐ 因此只需要将后面的「大数」与前面的「小数」交换，就能得到一个更大的数。比如 123456，将 5 和 6 交换就能得到一个更大的数 123465。

我们还希望下一个数增加的幅度尽可能的小，这样才满足“下一个排列与当前排列紧邻“的要求。为了满足这个要求，我们需要：

• 在尽可能靠右的低位进行交换，需要从后向前查找
• 将一个 尽可能小的「大数」 与前面的「小数」交换。比如 123465，下一个排列应该把 5 和 4 交换而不是把 6 和 4 交换
• 将「大数」换到前面后，需要将「大数」后面的所有数重置为升序，因为升序排列是最小的排列。以 123465 为例：首先按照上一步，交换 5 和 4，得到 123564；然后需要将 5 之后的数重置为升序，得到 123546。显然 123546 比 123564 更小，123546 就是 123465 的下一个排列

算法过程如下：

• 从后向前查找第一个相邻升序的元素对 (i,j)，满足 A[i] < A[j]。此时 [j,end) 必然是降序
• 如果在步骤 1 找不到符合的相邻元素对，说明当前排列为降序排列，已经是最大数，则按照题意返回最小排列即直接逆置即可
• 在 [j,end) 从后向前查找第一个满足 A[i] < A[k] 的 k（也就是在 （i, end）中找到比 i 大的最小的一个数）。A[i]、A[k] 分别就是上文所说的「小数」、「大数」，将 A[i] 与 A[k] 交换
• 可以断定这时 [j,end) 必然是降序，逆置 [j,end)，使其升序，这样获得的数字就是最小的

class Solution {
    public void nextPermutation(int[] nums) {
        // 1. 从后往前找第一个升序对 (nums[i], nums[i+1])
        int i = nums.length - 2;
        for (; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                break;
            }
        }

        // 如果不存在升序对，说明当前排列已经是最大，直接反转即可
        if (i == -1) {
            reverseArray(nums, 0, nums.length - 1);
            return ;
        }

        int j = i + 1;
        // 2. 此时 [j, end] 一定是降序的，在 [j, end] 中找到比 nums[i] 大的数
        // (或者说，从后往前 不超过 j 找到第一个比 nums[i] 大的数) 然后交换
        for (int k = nums.length - 1; k >= j; k--) {
            if (nums[k] > nums[i]) {
                int temp = nums[k];
                nums[k] = nums[i];
                nums[i] = temp;
                break;
            }
        }

        // 3. 反转 [j, end] 为升序
        reverseArray(nums, j, nums.length - 1);
    }

    // [left, right]
    private void reverseArray(int[] nums, int left, int right) {
        if (nums == null || nums.length == 0) {
            return;
        }

        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left ++;
            right --;
        }
    }
}

💥 复杂度分析

• 空间复杂度：O(1)
• 时间复杂度：O(N)