题目描述整数数组的一个排列就是将其所有成员以序列或线性顺序排列。例如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]输出[1,3,2]示例 2输入nums [3,2,1]输出[1,2,3]示例 3输入nums [1,1,5]输出[1,5,1]解题思路最优解法双指针 反转思路从右往左找第一个升序对nums[i] nums[i1]从右往左找第一个大于nums[i]的数nums[j]交换nums[i]和nums[j]然后反转i1到末尾具体过程示例nums [1, 2, 3]第1步: 从右往左找升序对 3 2? 是继续 2 1? 是继续 1 2? 是i 0nums[0]1 nums[1]2 第2步: 从右往左找第一个 nums[0]1 的数 3 1? 是j 2 第3步: 交换 nums[0] 和 nums[2] [3, 2, 1] 第4步: 反转 i11 到末尾 [3, 1, 2] ✅nums [3, 2, 1]第1步: 从右往左找升序对 2 1? 是 3 2? 是 没有升序对i -1 第2步: 直接反转整个数组 [1, 2, 3] ✅代码实现class Solution { public: void nextPermutation(vectorint nums) { int n nums.size(); // 第1步从右往左找第一个升序对 int i n - 2; while (i 0 nums[i] nums[i 1]) { i--; } // 第2步如果找到了升序对从右往左找第一个大于 nums[i] 的数 if (i 0) { int j n - 1; while (nums[j] nums[i]) { j--; } swap(nums[i], nums[j]); } // 第3步反转 i1 到末尾 reverse(nums.begin() i 1, nums.end()); } };复杂度分析维度复杂度说明时间复杂度O(n)最多遍历数组三次空间复杂度O(1)原地修改只用常数空间优缺点优点缺点✅ 时间复杂度 O(n)最优❌ 思路不直观需要理解字典序✅ 空间复杂度 O(1)原地修改❌ 边界条件多如i -1✅ 代码简洁❌ 容易写错交换和反转的范围总结要点说明最优解法三步走找升序对 → 找更大值交换 → 反转后缀时间复杂度O(n)空间复杂度O(1)关键步骤i从右往左找nums[i] nums[i1]边界处理i -1时直接反转整个数组