31 下一个排列

2026年3月13日

一、题目

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

例如，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, 3, 5, 4, 2] 看作 13542。我们要找比它大一点点的数。

第一步：从右向左，找第一个“非递增”的数字（找拐点）

我们从右往左看，2 -> 4 -> 5 都是递增的，这说明右边这部分已经是最大的排列了，没法再变大了。
继续往左走，发现 3 比 5 小！这就是我们要修改的位置。我们称 3 为较小数（记为索引 i）。

第二步：从右向左，找第一个比“较小数”大的数字

既然要把 3 变大，我们需要从右边的 [5, 4, 2] 中找一个刚好大于 3 的数字来替换它。
因为右边是降序的，我们只要再从右往左遍历，找到的第一个大于 3 的数字，就是刚好大于它的数。
在 [5, 4, 2] 中从右往左看，第一个大于 3 的是 4。我们称 4 为较大数（记为索引 j）。

第三步：交换这两个数字

把 3 和 4 交换位置。现在的排列变成了 [1, 4, 5, 3, 2]。
现在前面的部分变大了（13... 变成了 14...），符合要求。

第四步：将后面的数字反转为升序

交换后，原来 3 右边的部分 [5, 3, 2] 依然是降序的，也就是这部分排列是最大的。
为了让整个排列“刚刚好”比原来大，我们需要把这部分变成最小的，也就是升序。
只需要把 [5, 3, 2] 反转成 [2, 3, 5] 即可。
最终结果：[1, 4, 2, 3, 5]。

(特殊情况：如果第一步一直走到头都没找到较小数，说明整个数组是完全降序的，比如 [3, 2, 1]，这就是最大排列。直接跳到第四步把整个数组反转为 [1, 2, 3] 即可。)

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

        // 1. 从后向前找第一个升序对 (nums[i] < nums[i+1])
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        // 此时如果 i >= 0，说明找到了“较小数” nums[i]
        // 如果 i < 0，说明整个数组是降序的，直接跳过寻找较大数和交换，去反转整个数组
        if (i >= 0) {
            // 2. 再次从后向前找第一个比 nums[i] 大的数
            int j = n - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            // 3. 交换 nums[i] 和 nums[j]
            swap(nums, i, j);
        }

        // 4. 将 nums[i+1] 到末尾的部分反转（使其变成升序）
        reverse(nums, i + 1, n - 1);
    }

    // 辅助方法：交换元素
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    // 辅助方法：反转数组指定区间的元素
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }
}

时间复杂度： $O(n)$ （最多一次从右向左扫描找较小数、一次找较大数、一次反转，均为线性）

空间复杂度： $O(1)$ （原地修改，只用常数个额外变量）

一、题目

二、题解

评论