LeetCode 31 下一个排列的 C 实现核心在于三步走策略从右往左找第一个升序位置、交换右侧刚好更大的数、反转后缀时间复杂度 O(n)空间复杂度 O(1)。算法思路三步走以 [1,2,7,4,3,1] 为例目标是找到刚好比它大的下一个排列从右往左找第一个 nums[i] nums[i1] 的位置这一步找到的是还有上升空间的最右位置示例中2 7所以 i 1值为 2此时 i 右侧一定是降序的在右侧降序区中从右往左找第一个比 nums[i] 大的数交换右侧降序区 [7,4,3,1] 中从右往左第一个比 2 大的是 3交换 2 和 3 → [1,3,7,4,2,1]反转 i 之后的部分使其变为升序最小排列反转 [7,4,2,1] → [1,2,4,7]最终结果[1,3,1,2,4,7] ✅如果第 1 步找不到整个数组降序说明已是最大排列直接反转整个数组即可。C 代码实现class Solution {public:void nextPermutation(vector nums) {int n nums.size();int i n - 2;// 第一步从右往左找第一个 nums[i] nums[i1] while (i 0 nums[i] nums[i 1]) { i--; } // 第二步如果找到了在右侧找刚好比 nums[i] 大的数并交换 if (i 0) { int j n - 1; while (nums[j] nums[i]) { j--; } swap(nums[i], nums[j]); } // 第三步反转 i 之后的部分降序变升序 reverse(nums.begin() i 1, nums.end()); }};执行流程图解以 [4,5,2,6,3,1] 为例原始数组[4, 5, 2, 6, 3, 1]第一步从右往左找第一个 nums[i] nums[i1]6 3 1 都是降序到 2 6 停止i 2值为 2第二步在右侧 [6,3,1] 中从右往左找第一个 2 的数1 ≤ 23 2 → j 4值为 3交换 nums[2] 和 nums[4]→ [4, 5, 3, 6, 2, 1]第三步反转 i1 之后的部分 [6,2,1] → [1,2,6]→ [4, 5, 3, 1, 2, 6] ✅复杂度分析维度 复杂度 说明时间复杂度 O(n) 最多遍历数组两遍空间复杂度 O(1) 原地修改只用常数空间关键细节为什么反转而不是排序 交换后 i 右侧仍然是降序的反转即可得到升序比排序更高效O(n) vs O(n log n)。为什么从右往左找 越靠右改动对高位的影响越小保证变大的幅度最小。 而非 题目允许重复元素用 可以正确处理如 [1,1,5] 这类情况。这道题的算法也是 C 标准库 std::next_permutation 的底层实现原理掌握后可以直接理解 STL 源码。需要我帮你整理一个 C 全排列/下一个排列的通用模板吗刷题时直接套很省事。