算法详解：整数数组的下一个排列——从思路到实现（力扣第31题思路）-程序员充电站

在算法学习中，字典序相关的问题常常考验我们对“有序性”的理解，而“整数数组的下一个排列”就是这类问题中的经典代表。它不仅要求我们找到符合规则的排列，还对空间复杂度提出了严格限制——必须原地修改且仅用常数额外空间。今天，我们就从题目本质出发，一步步拆解思路，最终实现高效解决方案。

一、题目解读：什么是“下一个排列”？

首先要明确核心概念：数组的“下一个排列”是指其字典序更大的排列。如果把数组的所有排列按字典序从小到大排序，下一个排列就是当前排列的“后继”；若当前排列已是最大（如[3,2,1]），则需返回字典序最小的排列（即升序排列[1,2,3]）。

举几个例子帮助理解：

输入[1,2,3]，下一个排列是[1,3,2]（字典序稍大）；
输入[2,3,1]，下一个排列是[3,1,2]（突破原有前缀，构建更大组合）；
输入[3,2,1]，无更大排列，返回[1,2,3]。

题目关键约束：原地修改（不能新建数组）、常数空间（额外变量个数固定，与数组长度无关），这是我们设计算法的核心限制。

二、核心思路：从“降序”中找突破口

字典序的核心是“前缀相同，后续更大”。如果数组从后往前是升序的，说明这部分元素已无法通过调整得到更大排列；只有当出现“降序断点”时，才存在调整的可能。基于此，我们可以归纳出解决步骤：

步骤1：找到第一个“降序断点”k

从数组末尾开始向前遍历，找到第一个满足nums[k] < nums[k+1]的索引k。这意味着：

k之后的元素（nums[k+1..n-1]）是降序排列的，无法通过调整这部分元素得到更大排列；
k是第一个可以通过修改来提升字典序的位置——我们需要用k之后的某个更大元素替换nums[k]。

若遍历完未找到这样的k（即k=-1），说明整个数组是降序的，直接反转数组即可得到最小排列。

步骤2：找到k之后“最小的更大元素”l

既然k之后的元素是降序的，从末尾向前遍历，第一个满足nums[l] > nums[k]的索引l，就是k之后比nums[k]大的最小元素。选择这个元素交换，能保证替换后得到的排列是“最小的更大排列”（避免跳过大的中间排列）。

步骤3：交换并反转后续元素

1. 交换nums[k]和nums[l]：此时k位置的元素已更新为更大的值，保证了排列的字典序提升；

2. 反转nums[k+1..n-1]：由于交换前k之后是降序，交换后这部分仍为降序，反转后变为升序，能确保后续元素构成“最小的可能组合”，最终得到下一个排列。

三、完整代码实现（C++）

结合上述思路，我们可以写出简洁高效的代码，完全满足“原地修改”和“常数空间”的要求：

#include <vector> #include <algorithm> // 包含reverse和swap函数 using namespace std; class Solution { public: void nextPermutation(vector<int>& nums) { int n = nums.size(); int k = -1; // 降序断点索引，初始为-1表示未找到 // 步骤1：找到第一个nums[k] < nums[k+1]的k for (int i = n - 2; i >= 0; --i) { if (nums[i] < nums[i + 1]) { k = i; break; } } // 步骤2：若未找到断点，说明数组降序，直接反转 if (k == -1) { reverse(nums.begin(), nums.end()); return; } // 步骤3：找到k之后第一个比nums[k]大的元素索引l int l = -1; for (int i = n - 1; i > k; --i) { if (nums[i] > nums[k]) { l = i; break; } } // 步骤4：交换k和l位置的元素 swap(nums[k], nums[l]); // 步骤5：反转k之后的元素，将降序转为升序 reverse(nums.begin() + k + 1, nums.end()); } };

四、代码逐段解析

1. 初始化与断点查找

用n记录数组长度，k初始化为-1（标记未找到断点）。从n-2开始向前遍历（因为要比较i和i+1），一旦发现nums[i] < nums[i+1]，立即记录k=i并退出循环——这是效率最高的查找方式，无需遍历整个数组。

2. 全降序处理

若k仍为-1，说明数组从左到右是降序的（如[3,2,1]），此时反转整个数组即可得到最小排列，这一步时间复杂度为O(n)。

3. 查找交换元素l

从数组末尾向前遍历（k之后是降序，末尾元素最小），第一个比nums[k]大的元素就是我们需要的l——这样能确保交换后k位置的元素提升幅度最小，符合“下一个排列”的定义。

4. 交换与反转

swap函数是C++标准库函数，实现常数时间的元素交换；reverse函数反转k之后的元素，将降序转为升序，确保后续元素是最小组合，这一步时间复杂度为O(n)。

五、复杂度分析

时间复杂度：O(n)。整个过程包含3次遍历（找k、找l、反转），每次遍历的时间都与数组长度线性相关，且无嵌套循环。
空间复杂度：O(1)。仅使用了k、l、n三个额外变量，未开辟新的数组或数据结构，完全满足题目“常数空间”的要求。

六、测试用例验证

我们用题目给出的示例验证代码正确性：

示例1：输入[1,2,3]
1. 找k：i=1时，nums[1]=2 < nums[2]=3，k=1；
2. 找l：i=2时，nums[2]=3 > nums[1]=2，l=2；
3. 交换后：[1,3,2]；反转k之后（仅元素2），结果仍为[1,3,2]，符合预期。
示例2：输入[3,2,1]
1. 找k：遍历后k=-1，反转数组得到[1,2,3]，符合预期。
示例3：输入[1,1,5]
1. 找k：i=1时，nums[1]=1 < nums[2]=5，k=1；
2. 找l：i=2时，nums[2]=5 > nums[1]=1，l=2；
3. 交换后：[1,5,1]；反转k之后（仅元素1），结果仍为[1,5,1]，符合预期。