LC 31. 下一个排列

题目描述

这是 LeetCode 上的 31. 下一个排列 ，难度为 中等。

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

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

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

示例 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]

提示：

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

---

模拟

找下一个排列的数，大家可以先想想大脑来是怎么完成这个找数的过程的。

我们会尽可能的将低位的数字变大，这样才符合「下一个排列」的定义。

也就是从低位往高位检查，观察某一位在「下一个排列」中是否可以被更大的数代替。

那么如何判断某一位能够被更大的数代替呢？

其实就是将 k 位到低位的所有数作为候选，判断是否有更大的数可以填入 k 位中。

假设当前我们检查到 k 位，要分析第 k 位在「下一个排列」中是否能被更大的数代替。

我们会先假定高位到 k 位的数不变，在 k 位到低位中是否有比 k 位上的数更大的数，如果有说明 k 在「下一个排列」中变大。

换句话说，我们要找的第 k 位其实就是从低位到高位的第一个下降的数。

…

为了更好理解，我们结合样例来分析，假设样例为 [1,3,5,4,1]：

1. 从后往前找，找到第一个下降的位置，记为 k。注意k 以后的位置是降序的。 在样例中就是找到 3

2. 从 k 往后找，找到最小的比 k 要大的数。 找到 4

3. 将两者交换。注意此时 k 以后的位置仍然是降序的。

4. 直接将 k 以后的部分翻转（变为升序）。

注意：如果在步骤 1 中找到头部还没找到，说明该序列已经是字典序最大的排列。按照题意，我们要将数组重新排列成最小的排列。

代码：

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length, k = n - 1;
        while (k - 1 >= 0 && nums[k - 1] >= nums[k]) k--;
        if (k == 0) {
            reverse(nums, 0, n - 1);
        } else {
            int u = k;
            while (u + 1 < n && nums[u + 1] > nums[k - 1]) u++;
            swap(nums, k - 1, u);
            reverse(nums, k, n - 1);
        }
    }
    void reverse(int[] nums, int a, int b) {
        int l = a, r = b;
        while (l < r) swap(nums, l++, r--);
    }
    void swap(int[] nums, int a, int b) {
        int c = nums[a];
        nums[a] = nums[b];
        nums[b] = c;
    }
}

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

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.31 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。