【刷穿 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;
        int 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;
    }
}

• 时间复杂度：对数组线性遍历。复杂度为

• 空间复杂度：

最后

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

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

由于 LeetCode 的题目随着周赛 & 双周赛不断增加，为了方便我们统计进度，我们将按照系列起始时的总题数作为分母，完成的题目作为分子，进行进度计算。当前进度为 31/1916 。

为了方便各位同学能够电脑上进行调试和提交代码，我在 Github 建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode。在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。