031.下一个排列

作者：沉默王二
发布时间：2024-02-29T16:32:40.605+0800

---

技术派阅读地址：https://paicoding.com/column/7/31

• 语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu

• 这道题可以说完全重写了，给出 2 道大家完全都能掌握的题解（先从右往左找，找到 num i < num i+1 确定 i 的位置，再从右往左找，找到 num j > num i，交换它们的顺序，再对 num i 之后的元素进行升序排列）。

• 增加代码注释，这样大家更容易看懂并掌握题解；

• 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；

• 增加手绘图，这样大家更容易理解解题思路；

• 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；

• 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；

• 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。

• 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

鲁迅说过，这是 2 月的最后一天了，3 月将迎来社招的高峰期，以及春招的高峰期，希望大家都能坚持住，别掉队。二哥的 LeetCode 刷题会继续陪伴大家，希望能给大家带去更多解题的思路，以及学习 Java 的乐趣。

题意

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

例如，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]

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

分析 1

这道题看起来很唬人，比如题目描述中提到的“字典序”，很多球友第一眼看到这个名词的时候会有点懵，这里简单解释一下。

字典序（dictionary order），又称 字母序（alphabetical order），原意是表示英文单词在字典中的先后顺序，在计算机领域中扩展成两个任意字符串的大小关系。

在这道题目中，字典序其实是指☞ 数字大小的先后顺序。

理解了“字典序”，就能很快理解这道题的题意了：要我们求出比这个数更大的一个排列，比如 123，比它大的是 132，对吧？只需要改变 23 的位置就可以了。312 也比 123 大，只不过它是比 132 更大的一个，不是比 123 更大的一个，官大一级压死人，一级一级来压（😂）。

就好像我们在打扑克牌，我出了一个对 10，那你出对 11 就压住我了，没必要把手里的对 12 先出来，对吧？

再比如 321 已经是「1、2、3」 这三个数字组合中最大的那个了，那就等于说没有更大的了，所以返回 123 这个最小的。

明白了吧？

要想解题，首先得明白题意，所以语文理解是非常重要的，其次是经验（😁）。

那凭借我们以往的经验，可能一下子会想到全排列。就拿 1、2、3、4 来举例吧，全排列如下：

nums=[1,2,3,4]

nums=[1,3,2,4]nums=[1,3,4,2]nums=[1,4,2,3]nums=[1,4,3,2]nums=[2,1,3,4]nums=[2,1,4,3]nums=[2,3,1,4]nums=[2,3,4,1]nums=[2,4,1,3]nums=[2,4,3,1]nums=[3,1,2,4]nums=[3,1,4,2]nums=[3,2,1,4]nums=[3,2,4,1]nums=[3,4,1,2]nums=[3,4,2,1]nums=[4,1,2,3]nums=[4,1,3,2]nums=[4,2,1,3]nums=[4,2,3,1]nums=[4,3,1,2]nums=[4,3,2,1]

观察nums = [1,3,4,2] -> nums = [1,4,2,3]这一步，因为4比3大，且4的位置在3之后，所以将4与3交换，必然能够使得nums变大，交换了之后，则变成了nums = [1,4,3,2]。

但显然这不是最小的比nums = [1,3,4,2]大的一个排列，我们还要把3和2的位置再翻转一下，才能得到nums = [1,4,2,3]这个 恰好 比nums = [1,3,4,2]大一点的排列。

那到底该怎么去找到这个 恰好 比nums大一点的排列呢？

第一步，我们可以从右向左查找第一个升序的相邻数字对 (i, i+1)，满足 nums[i] < nums[i+1]。

这意味着从 i+1 到末尾的数字都是降序的。如果找不到这样的 i（即整个数组是降序的），这说明当前排列已经是最大的排列，我们只需将其翻转为最小排列即可。

这一步完成之后，并不能保证我们得到的排列就是 恰好 比nums大一点的排列。

第二步，我们还要对nums[i+1] 到 nums[nums.length - 1]这个区间进行翻转，使得它变成升序排列，这样才能得到 恰好 比nums大一点的排列。

比如说上面提到的 [1,4,3,2]，i+1（i=1）到末尾的部分是 32。这部分是降序的。为了得到下一个排列，我们需要这部分变成升序。我们需要将这部分翻转，变成 23。

所以到这里，这道题目就迎刃而解了。具体代码实现：

class Solution {

    // 步骤1：从右向左查找第一个升序的相邻数字对(i, i+1)，满足nums[i] < nums[i+1]。        int i = nums.length - 2;        while (i >= 0 && nums[i] >= nums[i + 1]) {            i--;        }
    if (i >= 0) {            // 步骤2：在nums[i+1:]中从右向左找到第一个大于nums[i]的数字nums[j]。            int j = nums.length - 1;            while (j >= 0 && nums[i] >= nums[j]) {                j--;            }            // 步骤3：交换nums[i]和nums[j]。            swap(nums, i, j);        }
    // 步骤4：将nums[i+1:]翻转，使其变为升序。        reverse(nums, i + 1);    }
// 用于交换数组中两个元素的位置    private void swap(int[] nums, int i, int j) {        int temp = nums[i];        nums[i] = nums[j];        nums[j] = temp;    }
// 用于将数组的一部分翻转，即将nums[start:]变为升序    private void reverse(int[] nums, int start) {        int end = nums.length - 1;        while (start < end) {            swap(nums, start, end);            start++;            end--;        }    }}

为了更清晰地理解题解代码，我们将其拆分成几个关键部分，并逐一说明每部分的作用和逻辑。

1.寻找升序对 (i, i+1)

int i = nums.length - 2;

i--;}

• 目的：从数组的右端开始向左扫描，寻找第一个升序的相邻数字对，即找到第一个nums[i] < nums[i + 1]的位置。这个位置i是需要进行调整的起点，因为nums[i]右边的序列是降序的，没有更大的排列空间。
• 逻辑：使用一个while循环从右向左遍历数组，直到找到满足升序条件的i。

2.在 nums[i+1:] 中找到第一个大于 nums[i] 的数字并交换

nums[i+1:] 是指从i+1到数组末尾的部分。

if (i >= 0) {

while (j >= 0 && nums[i] >= nums[j]) {        j--;    }    swap(nums, i, j);}

• 目的：如果找到了这样的i，则在其右侧找到第一个大于nums[i]的数字nums[j]，然后交换nums[i]和nums[j]。这一步是为了在当前排列的基础上得到下一个稍大的数字。
• 逻辑：通过向左扫描数组的剩余部分来查找j，一旦找到就执行交换。

3.翻转 nums[i+1:] 使其升序

reverse(nums, i + 1);

• 目的：交换nums[i]和nums[j]后，i之后的序列仍然保持降序。为了获得下一个排列，需要将这个序列翻转成升序，这样从i+1到数组末尾就构成了最小的排列，确保整个数组是下一个更大的排列。
• 逻辑：从i+1开始到数组末尾，执行翻转操作，使其成为升序。

4.交换方法 swap

private void swap(int[] nums, int i, int j) {

nums[i] = nums[j];    nums[j] = temp;}

交换数组中两个位置的元素。

5.翻转方法 reverse

private void reverse(int[] nums, int start) {

while (start < end) {        swap(nums, start, end);        start++;        end--;    }}

将数组从指定位置start到数组末尾的部分翻转，使其成为升序。

效率嘛，自然是快得飞起。

分析 2

其实在 Java 中，Arrays.sort 方法可以来辅助完成排序/反转的工作。

比如说 [4,3,2,1]，我们直接对他进行 sort 排序，就会得到 [1,2,3,4]，对吧？

也就是说，如果不存在下一个更大的排列，那么，我们可以使用 sort 方法将这个数组重排为字典序最小的排列（即，其元素按升序排列）。

除此之外，在分析 1 中，我们需要对剩余的整数进行升序排列时，我们使用了一个 reverse 方法，其实我们可以直接使用 Arrays.sort (nums, i + 1, nums.length ) 来完成翻转的工作。

所以，我们可以将代码改写为：

class Solution {

    boolean found = false;        for (int i = nums.length - 2; i >= 0; i--) {            if (nums[i] < nums[i + 1]) {                // 从右向左寻找第一个大于nums[i]的数字                for (int j = nums.length - 1; j > i; j--) {                    if (nums[j] > nums[i]) {                        // 交换nums[i]和nums[j]                        swap(nums, i, j);                        // 将i+1到数组末尾的部分进行排序                        Arrays.sort(nums, i + 1, nums.length);                        found = true;                        break;                    }                }                if (found) break;            }        }        // 如果没有找到升序对，说明数组是降序的，直接排序得到最小排列        if (!found) {            Arrays.sort(nums);        }    }
// 交换数组中的两个元素    private void swap(int[] nums, int i, int j) {        int temp = nums[i];        nums[i] = nums[j];        nums[j] = temp;    }}

实现步骤上其实差不多：

• 第一步，从右向左寻找第一个升序对 (i, i+1)，满足 nums[i] < nums[i+1]。
• 第二步，从右向左寻找第一个大于 nums[i] 的数字 nums[j]，并交换 nums[i] 和 nums[j]。
• 第三步，将 nums[i+1] 以后的元素进行排序。

因为排序的效率没有反转来得直接，所以效率下降了一些，但应该是更好理解了。

总结

这道题目的难点其实在于字典序的理解，一旦理解之后，整个题目的解法就不算是特别难了。

涉及到的 Java 基础知识也不多：

• **数组 **的遍历
• Arrays 类

力扣链接：https://leetcode.cn/problems/next-permutation/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100 天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4600+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

技术派阅读地址：https://paicoding.com/column/7/31

• 语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu

• 这道题可以说完全重写了，给出 2 道大家完全都能掌握的题解（先从右往左找，找到 num i < num i+1 确定 i 的位置，再从右往左找，找到 num j > num i，交换它们的顺序，再对 num i 之后的元素进行升序排列）。

• 增加代码注释，这样大家更容易看懂并掌握题解；

• 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；

• 增加手绘图，这样大家更容易理解解题思路；

• 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；

• 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；

• 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。

• 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

鲁迅说过，这是 2 月的最后一天了，3 月将迎来社招的高峰期，以及春招的高峰期，希望大家都能坚持住，别掉队。二哥的 LeetCode 刷题会继续陪伴大家，希望能给大家带去更多解题的思路，以及学习 Java 的乐趣。

题意

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

例如，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]

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

分析 1

这道题看起来很唬人，比如题目描述中提到的“字典序”，很多球友第一眼看到这个名词的时候会有点懵，这里简单解释一下。

字典序（dictionary order），又称 字母序（alphabetical order），原意是表示英文单词在字典中的先后顺序，在计算机领域中扩展成两个任意字符串的大小关系。

在这道题目中，字典序其实是指☞ 数字大小的先后顺序。

理解了“字典序”，就能很快理解这道题的题意了：要我们求出比这个数更大的一个排列，比如 123，比它大的是 132，对吧？只需要改变 23 的位置就可以了。312 也比 123 大，只不过它是比 132 更大的一个，不是比 123 更大的一个，官大一级压死人，一级一级来压（😂）。

就好像我们在打扑克牌，我出了一个对 10，那你出对 11 就压住我了，没必要把手里的对 12 先出来，对吧？

再比如 321 已经是「1、2、3」 这三个数字组合中最大的那个了，那就等于说没有更大的了，所以返回 123 这个最小的。

明白了吧？

要想解题，首先得明白题意，所以语文理解是非常重要的，其次是经验（😁）。

那凭借我们以往的经验，可能一下子会想到全排列。就拿 1、2、3、4 来举例吧，全排列如下：

nums=[1,2,3,4]

nums=[1,3,2,4]nums=[1,3,4,2]nums=[1,4,2,3]nums=[1,4,3,2]nums=[2,1,3,4]nums=[2,1,4,3]nums=[2,3,1,4]nums=[2,3,4,1]nums=[2,4,1,3]nums=[2,4,3,1]nums=[3,1,2,4]nums=[3,1,4,2]nums=[3,2,1,4]nums=[3,2,4,1]nums=[3,4,1,2]nums=[3,4,2,1]nums=[4,1,2,3]nums=[4,1,3,2]nums=[4,2,1,3]nums=[4,2,3,1]nums=[4,3,1,2]nums=[4,3,2,1]

观察nums = [1,3,4,2] -> nums = [1,4,2,3]这一步，因为4比3大，且4的位置在3之后，所以将4与3交换，必然能够使得nums变大，交换了之后，则变成了nums = [1,4,3,2]。

但显然这不是最小的比nums = [1,3,4,2]大的一个排列，我们还要把3和2的位置再翻转一下，才能得到nums = [1,4,2,3]这个 恰好 比nums = [1,3,4,2]大一点的排列。

那到底该怎么去找到这个 恰好 比nums大一点的排列呢？

第一步，我们可以从右向左查找第一个升序的相邻数字对 (i, i+1)，满足 nums[i] < nums[i+1]。

这意味着从 i+1 到末尾的数字都是降序的。如果找不到这样的 i（即整个数组是降序的），这说明当前排列已经是最大的排列，我们只需将其翻转为最小排列即可。

这一步完成之后，并不能保证我们得到的排列就是 恰好 比nums大一点的排列。

第二步，我们还要对nums[i+1] 到 nums[nums.length - 1]这个区间进行翻转，使得它变成升序排列，这样才能得到 恰好 比nums大一点的排列。

比如说上面提到的 [1,4,3,2]，i+1（i=1）到末尾的部分是 32。这部分是降序的。为了得到下一个排列，我们需要这部分变成升序。我们需要将这部分翻转，变成 23。

所以到这里，这道题目就迎刃而解了。具体代码实现：

class Solution {

    // 步骤1：从右向左查找第一个升序的相邻数字对(i, i+1)，满足nums[i] < nums[i+1]。        int i = nums.length - 2;        while (i >= 0 && nums[i] >= nums[i + 1]) {            i--;        }
    if (i >= 0) {            // 步骤2：在nums[i+1:]中从右向左找到第一个大于nums[i]的数字nums[j]。            int j = nums.length - 1;            while (j >= 0 && nums[i] >= nums[j]) {                j--;            }            // 步骤3：交换nums[i]和nums[j]。            swap(nums, i, j);        }
    // 步骤4：将nums[i+1:]翻转，使其变为升序。        reverse(nums, i + 1);    }
// 用于交换数组中两个元素的位置    private void swap(int[] nums, int i, int j) {        int temp = nums[i];        nums[i] = nums[j];        nums[j] = temp;    }
// 用于将数组的一部分翻转，即将nums[start:]变为升序    private void reverse(int[] nums, int start) {        int end = nums.length - 1;        while (start < end) {            swap(nums, start, end);            start++;            end--;        }    }}

为了更清晰地理解题解代码，我们将其拆分成几个关键部分，并逐一说明每部分的作用和逻辑。

1.寻找升序对 (i, i+1)

int i = nums.length - 2;

i--;}

• 目的：从数组的右端开始向左扫描，寻找第一个升序的相邻数字对，即找到第一个nums[i] < nums[i + 1]的位置。这个位置i是需要进行调整的起点，因为nums[i]右边的序列是降序的，没有更大的排列空间。
• 逻辑：使用一个while循环从右向左遍历数组，直到找到满足升序条件的i。

2.在 nums[i+1:] 中找到第一个大于 nums[i] 的数字并交换

nums[i+1:] 是指从i+1到数组末尾的部分。

if (i >= 0) {

while (j >= 0 && nums[i] >= nums[j]) {        j--;    }    swap(nums, i, j);}

• 目的：如果找到了这样的i，则在其右侧找到第一个大于nums[i]的数字nums[j]，然后交换nums[i]和nums[j]。这一步是为了在当前排列的基础上得到下一个稍大的数字。
• 逻辑：通过向左扫描数组的剩余部分来查找j，一旦找到就执行交换。

3.翻转 nums[i+1:] 使其升序

reverse(nums, i + 1);

• 目的：交换nums[i]和nums[j]后，i之后的序列仍然保持降序。为了获得下一个排列，需要将这个序列翻转成升序，这样从i+1到数组末尾就构成了最小的排列，确保整个数组是下一个更大的排列。
• 逻辑：从i+1开始到数组末尾，执行翻转操作，使其成为升序。

4.交换方法 swap

private void swap(int[] nums, int i, int j) {

nums[i] = nums[j];    nums[j] = temp;}

交换数组中两个位置的元素。

5.翻转方法 reverse

private void reverse(int[] nums, int start) {

while (start < end) {        swap(nums, start, end);        start++;        end--;    }}

将数组从指定位置start到数组末尾的部分翻转，使其成为升序。

效率嘛，自然是快得飞起。

分析 2

其实在 Java 中，Arrays.sort 方法可以来辅助完成排序/反转的工作。

比如说 [4,3,2,1]，我们直接对他进行 sort 排序，就会得到 [1,2,3,4]，对吧？

也就是说，如果不存在下一个更大的排列，那么，我们可以使用 sort 方法将这个数组重排为字典序最小的排列（即，其元素按升序排列）。

除此之外，在分析 1 中，我们需要对剩余的整数进行升序排列时，我们使用了一个 reverse 方法，其实我们可以直接使用 Arrays.sort (nums, i + 1, nums.length ) 来完成翻转的工作。

所以，我们可以将代码改写为：

class Solution {

    boolean found = false;        for (int i = nums.length - 2; i >= 0; i--) {            if (nums[i] < nums[i + 1]) {                // 从右向左寻找第一个大于nums[i]的数字                for (int j = nums.length - 1; j > i; j--) {                    if (nums[j] > nums[i]) {                        // 交换nums[i]和nums[j]                        swap(nums, i, j);                        // 将i+1到数组末尾的部分进行排序                        Arrays.sort(nums, i + 1, nums.length);                        found = true;                        break;                    }                }                if (found) break;            }        }        // 如果没有找到升序对，说明数组是降序的，直接排序得到最小排列        if (!found) {            Arrays.sort(nums);        }    }
// 交换数组中的两个元素    private void swap(int[] nums, int i, int j) {        int temp = nums[i];        nums[i] = nums[j];        nums[j] = temp;    }}

实现步骤上其实差不多：

• 第一步，从右向左寻找第一个升序对 (i, i+1)，满足 nums[i] < nums[i+1]。
• 第二步，从右向左寻找第一个大于 nums[i] 的数字 nums[j]，并交换 nums[i] 和 nums[j]。
• 第三步，将 nums[i+1] 以后的元素进行排序。

因为排序的效率没有反转来得直接，所以效率下降了一些，但应该是更好理解了。

总结

这道题目的难点其实在于字典序的理解，一旦理解之后，整个题目的解法就不算是特别难了。

涉及到的 Java 基础知识也不多：

• **数组 **的遍历
• Arrays 类

力扣链接：https://leetcode.cn/problems/next-permutation/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100 天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4600+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

技术派阅读地址：https://paicoding.com/column/7/31

• 语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu

• 这道题可以说完全重写了，给出 2 道大家完全都能掌握的题解（先从右往左找，找到 num i < num i+1 确定 i 的位置，再从右往左找，找到 num j > num i，交换它们的顺序，再对 num i 之后的元素进行升序排列）。

• 增加代码注释，这样大家更容易看懂并掌握题解；

• 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；

• 增加手绘图，这样大家更容易理解解题思路；

• 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；

• 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；

• 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。

• 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

鲁迅说过，这是 2 月的最后一天了，3 月将迎来社招的高峰期，以及春招的高峰期，希望大家都能坚持住，别掉队。二哥的 LeetCode 刷题会继续陪伴大家，希望能给大家带去更多解题的思路，以及学习 Java 的乐趣。

题意

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

例如，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]

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

分析 1

这道题看起来很唬人，比如题目描述中提到的“字典序”，很多球友第一眼看到这个名词的时候会有点懵，这里简单解释一下。

字典序（dictionary order），又称 字母序（alphabetical order），原意是表示英文单词在字典中的先后顺序，在计算机领域中扩展成两个任意字符串的大小关系。

在这道题目中，字典序其实是指☞ 数字大小的先后顺序。

理解了“字典序”，就能很快理解这道题的题意了：要我们求出比这个数更大的一个排列，比如 123，比它大的是 132，对吧？只需要改变 23 的位置就可以了。312 也比 123 大，只不过它是比 132 更大的一个，不是比 123 更大的一个，官大一级压死人，一级一级来压（😂）。

就好像我们在打扑克牌，我出了一个对 10，那你出对 11 就压住我了，没必要把手里的对 12 先出来，对吧？

再比如 321 已经是「1、2、3」 这三个数字组合中最大的那个了，那就等于说没有更大的了，所以返回 123 这个最小的。

明白了吧？

要想解题，首先得明白题意，所以语文理解是非常重要的，其次是经验（😁）。

那凭借我们以往的经验，可能一下子会想到全排列。就拿 1、2、3、4 来举例吧，全排列如下：

nums=[1,2,3,4]

nums=[1,3,2,4]nums=[1,3,4,2]nums=[1,4,2,3]nums=[1,4,3,2]nums=[2,1,3,4]nums=[2,1,4,3]nums=[2,3,1,4]nums=[2,3,4,1]nums=[2,4,1,3]nums=[2,4,3,1]nums=[3,1,2,4]nums=[3,1,4,2]nums=[3,2,1,4]nums=[3,2,4,1]nums=[3,4,1,2]nums=[3,4,2,1]nums=[4,1,2,3]nums=[4,1,3,2]nums=[4,2,1,3]nums=[4,2,3,1]nums=[4,3,1,2]nums=[4,3,2,1]

观察nums = [1,3,4,2] -> nums = [1,4,2,3]这一步，因为4比3大，且4的位置在3之后，所以将4与3交换，必然能够使得nums变大，交换了之后，则变成了nums = [1,4,3,2]。

但显然这不是最小的比nums = [1,3,4,2]大的一个排列，我们还要把3和2的位置再翻转一下，才能得到nums = [1,4,2,3]这个 恰好 比nums = [1,3,4,2]大一点的排列。

那到底该怎么去找到这个 恰好 比nums大一点的排列呢？

第一步，我们可以从右向左查找第一个升序的相邻数字对 (i, i+1)，满足 nums[i] < nums[i+1]。

这意味着从 i+1 到末尾的数字都是降序的。如果找不到这样的 i（即整个数组是降序的），这说明当前排列已经是最大的排列，我们只需将其翻转为最小排列即可。

这一步完成之后，并不能保证我们得到的排列就是 恰好 比nums大一点的排列。

第二步，我们还要对nums[i+1] 到 nums[nums.length - 1]这个区间进行翻转，使得它变成升序排列，这样才能得到 恰好 比nums大一点的排列。

比如说上面提到的 [1,4,3,2]，i+1（i=1）到末尾的部分是 32。这部分是降序的。为了得到下一个排列，我们需要这部分变成升序。我们需要将这部分翻转，变成 23。

所以到这里，这道题目就迎刃而解了。具体代码实现：

class Solution {

    // 步骤1：从右向左查找第一个升序的相邻数字对(i, i+1)，满足nums[i] < nums[i+1]。        int i = nums.length - 2;        while (i >= 0 && nums[i] >= nums[i + 1]) {            i--;        }
    if (i >= 0) {            // 步骤2：在nums[i+1:]中从右向左找到第一个大于nums[i]的数字nums[j]。            int j = nums.length - 1;            while (j >= 0 && nums[i] >= nums[j]) {                j--;            }            // 步骤3：交换nums[i]和nums[j]。            swap(nums, i, j);        }
    // 步骤4：将nums[i+1:]翻转，使其变为升序。        reverse(nums, i + 1);    }
// 用于交换数组中两个元素的位置    private void swap(int[] nums, int i, int j) {        int temp = nums[i];        nums[i] = nums[j];        nums[j] = temp;    }
// 用于将数组的一部分翻转，即将nums[start:]变为升序    private void reverse(int[] nums, int start) {        int end = nums.length - 1;        while (start < end) {            swap(nums, start, end);            start++;            end--;        }    }}

为了更清晰地理解题解代码，我们将其拆分成几个关键部分，并逐一说明每部分的作用和逻辑。

1.寻找升序对 (i, i+1)

int i = nums.length - 2;

i--;}

• 目的：从数组的右端开始向左扫描，寻找第一个升序的相邻数字对，即找到第一个nums[i] < nums[i + 1]的位置。这个位置i是需要进行调整的起点，因为nums[i]右边的序列是降序的，没有更大的排列空间。
• 逻辑：使用一个while循环从右向左遍历数组，直到找到满足升序条件的i。

2.在 nums[i+1:] 中找到第一个大于 nums[i] 的数字并交换

nums[i+1:] 是指从i+1到数组末尾的部分。

if (i >= 0) {

while (j >= 0 && nums[i] >= nums[j]) {        j--;    }    swap(nums, i, j);}

• 目的：如果找到了这样的i，则在其右侧找到第一个大于nums[i]的数字nums[j]，然后交换nums[i]和nums[j]。这一步是为了在当前排列的基础上得到下一个稍大的数字。
• 逻辑：通过向左扫描数组的剩余部分来查找j，一旦找到就执行交换。

3.翻转 nums[i+1:] 使其升序

reverse(nums, i + 1);

• 目的：交换nums[i]和nums[j]后，i之后的序列仍然保持降序。为了获得下一个排列，需要将这个序列翻转成升序，这样从i+1到数组末尾就构成了最小的排列，确保整个数组是下一个更大的排列。
• 逻辑：从i+1开始到数组末尾，执行翻转操作，使其成为升序。

4.交换方法 swap

private void swap(int[] nums, int i, int j) {

nums[i] = nums[j];    nums[j] = temp;}

交换数组中两个位置的元素。

5.翻转方法 reverse

private void reverse(int[] nums, int start) {

while (start < end) {        swap(nums, start, end);        start++;        end--;    }}

将数组从指定位置start到数组末尾的部分翻转，使其成为升序。

效率嘛，自然是快得飞起。

分析 2

其实在 Java 中，Arrays.sort 方法可以来辅助完成排序/反转的工作。

比如说 [4,3,2,1]，我们直接对他进行 sort 排序，就会得到 [1,2,3,4]，对吧？

也就是说，如果不存在下一个更大的排列，那么，我们可以使用 sort 方法将这个数组重排为字典序最小的排列（即，其元素按升序排列）。

除此之外，在分析 1 中，我们需要对剩余的整数进行升序排列时，我们使用了一个 reverse 方法，其实我们可以直接使用 Arrays.sort (nums, i + 1, nums.length ) 来完成翻转的工作。

所以，我们可以将代码改写为：

class Solution {

    boolean found = false;        for (int i = nums.length - 2; i >= 0; i--) {            if (nums[i] < nums[i + 1]) {                // 从右向左寻找第一个大于nums[i]的数字                for (int j = nums.length - 1; j > i; j--) {                    if (nums[j] > nums[i]) {                        // 交换nums[i]和nums[j]                        swap(nums, i, j);                        // 将i+1到数组末尾的部分进行排序                        Arrays.sort(nums, i + 1, nums.length);                        found = true;                        break;                    }                }                if (found) break;            }        }        // 如果没有找到升序对，说明数组是降序的，直接排序得到最小排列        if (!found) {            Arrays.sort(nums);        }    }
// 交换数组中的两个元素    private void swap(int[] nums, int i, int j) {        int temp = nums[i];        nums[i] = nums[j];        nums[j] = temp;    }}

实现步骤上其实差不多：

• 第一步，从右向左寻找第一个升序对 (i, i+1)，满足 nums[i] < nums[i+1]。
• 第二步，从右向左寻找第一个大于 nums[i] 的数字 nums[j]，并交换 nums[i] 和 nums[j]。
• 第三步，将 nums[i+1] 以后的元素进行排序。

因为排序的效率没有反转来得直接，所以效率下降了一些，但应该是更好理解了。

总结

这道题目的难点其实在于字典序的理解，一旦理解之后，整个题目的解法就不算是特别难了。

涉及到的 Java 基础知识也不多：

• **数组 **的遍历
• Arrays 类

力扣链接：https://leetcode.cn/problems/next-permutation/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100 天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4600+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412