下一个排列算法详解：LeetCode 31题解法与华为腾讯等大厂面试原题分析

今天我们来聊聊 LeetCode 的第 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]

提示：

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

问题分析

题目要求找出数字序列重新排列成字典序中 下一个更大的排列。举个例子，数字序列 213 的下一个排列是 231，而 231 的下一个排列则是 312。

那么，这道题的规律究竟怎么找呢？我们来看一组数字 [7,5,4,3,2]。这些数字从后往前看，是严格升序的（2->3->4->5->7）。对于这样的序列，无论怎么交换位置，都无法得到一个比当前排列更大的排列了，它已经是这部分数字能组成的最大排列。

我们再来看另一组数字 [1,4,7,6,5,3,2]。从后往前看，2->3->5->6->7 是升序的，但到了 7->4 这里就变成了降序。这个“降序点”4就是关键。直觉上，我们只需要把 4 和它后面比它大的某个数字交换，就能得到一个更大的排列。但题目要求的是“下一个更大”，也就是比原排列大且最小的那个。如果直接把 4 和最大的 7 交换，得到的 [1,7,4,6,5,3,2] 虽然变大了，但并不是“下一个”。

实际上，我们应该从后往前找到第一个比 4 大的数字。在升序序列 [2,3,5,6,7] 中，第一个比 4 大的是 5。交换 4 和 5，得到 [1,5,7,6,4,3,2]。这个排列肯定比原排列大，因为高位上的 5 大于 4。现在，为了让这个新排列尽可能小（即成为“下一个”），我们需要让 5 后面的数字序列保持最小可能。由于交换操作并没有改变后面数字 [7,6,4,3,2] 从后往前是升序的特性（即从前往后是降序），我们只需要将这部分序列反转，使其变成升序（最小排列）即可。所以最终 [1,4,7,6,5,3,2] 的下一个排列是 [1,5,2,3,4,6,7]。

为了更直观地理解这个过程，可以参考下面的示意图：

代码实现

Java 版本

public void nextPermutation(int[] nums) {
    int left = nums.length - 2;
    // 从后往前找第一个降序的元素
    while (left >= 0 && nums[left] >= nums[left + 1])
        left--;
    // 如果数组nums中的元素都是倒序，那么left就等于-1
    if (left >= 0) {
        int right = nums.length - 1;
        // 从后往前查找第一个比nums[left]大的值
        while (nums[right] <= nums[left])
            right--;
        swap(nums, left, right);
    }
    // 反转后面升序（从后往前看）的数字，使其变为最小排列
    reverse(nums, left + 1, nums.length - 1);
}

// 反转子数组[left，right]中的元素
private void reverse(int[] nums, int left, int right) {
    while (left < right)
        swap(nums, left++, right--);
}

// 交换数组中的两个数字
private void swap(int[] nums, int left, int right) {
    int tmp = nums[left];
    nums[left] = nums[right];
    nums[right] = tmp;
}

C++ 版本

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int left = nums.size() - 2;
        // 从后往前找第一个降序的元素
        while (left >= 0 && nums[left] >= nums[left + 1])
            left--;
        // 如果数组nums中的元素都是倒序，那么left就等于-1
        if (left >= 0) {
            int right = nums.size() - 1;
            // 从后往前查找第一个比nums[left]大的值
            while (nums[right] <= nums[left])
                right--;
            swap(nums[left], nums[right]);
        }
        // 反转后面升序（从后往前看）的数字，使其变为最小排列
        reverse(nums.begin() + left + 1, nums.end());
    }
};

总结

解决“下一个排列”问题的核心在于理解排列的字典序，并通过 双指针 技巧高效地定位需要交换和反转的边界。算法步骤如下：

1. 从后向前查找第一个相邻的升序对 (i, i+1)，满足 nums[i] < nums[i+1]。此时 i 左边的位置不变，i 右侧的序列是从后往前升序（即从前往后降序）。
2. 如果找不到这样的升序对，说明整个序列是降序的，没有下一个更大排列，直接将整个序列反转成升序即可。
3. 如果找到了 i，则再次从后向前查找第一个大于 nums[i] 的元素 nums[j]。
4. 交换 nums[i] 和 nums[j]。
5. 反转 i+1 到末尾的序列，使其变为升序，从而保证新排列是“下一个最小的更大排列”。

这道题考察了对数组顺序的深刻理解和双指针的灵活运用，是检验候选人基本功的经典题目。它之所以频繁出现在华为、腾讯等大厂的面试中，正是因为它能有效区分出那些只死记硬背和真正理解算法逻辑的求职者。希望这篇解析能帮助你彻底掌握它，在未来的技术面试中从容应对。如果你想查看更多算法题解或与更多开发者交流，欢迎访问云栈社区。