在算法学习中，字典序相关的问题常常考验我们对“有序性”的理解，而“整数数组的下一个排列”就是这类问题中的经典代表。它不仅要求我们找到符合规则的排列，还对空间复杂度提出了严格限制——必须原地修改且仅用常数额外空间。今天，我们就从题目本质出发，一步步拆解思路，最终实现高效解决方案。
一、题目解读：什么是“下一个排列”？
首先要明确核心概念：数组的“下一个排列”是指其字典序更大的排列。如果把数组的所有排列按字典序从小到大排序，下一个排列就是当前排列的“后继”；若当前排列已是最大（如[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]
找k：i=1时，nums[1]=2 < nums[2]=3，k=1；
找l：i=2时，nums[2]=3 > nums[1]=2，l=2；
交换后：[1,3,2]；反转k之后（仅元素2），结果仍为[1,3,2]，符合预期。
示例2：输入[3,2,1]
找k：遍历后k=-1，反转数组得到[1,2,3]，符合预期。
示例3：输入[1,1,5]
找k：i=1时，nums[1]=1 < nums[2]=5，k=1；
找l：i=2时，nums[2]=5 > nums[1]=1，l=2；
交换后：[1,5,1]；反转k之后（仅元素1），结果仍为[1,5,1]，符合预期。
七、总结与拓展
“下一个排列”问题的核心在于抓住“字典序”的本质——通过寻找“降序断点”确定调整位置，再通过“最小更大元素”和“反转”确保结果的合理性。这个思路不仅能解决本题，还能迁移到类似的字典序问题中，比如“上一个排列”（只需调整判断条件为找升序断点）。
在实际开发中，这类原地修改的算法常被用于优化空间开销，尤其在处理大规模数据时更为重要。掌握这种“从有序性中找突破口”的思维方式，能帮助我们更好地应对各类排列组合相关的算法问题。
如果你有其他测试用例或优化思路，欢迎在评论区交流讨论！