LeetCode 31. 下一个排列 — Rust 实现核心思路下一个排列遵循字典序规则分四步完成找拐点从右向左找到第一个左边小于右边的位置找替换数从右向左找到第一个大于拐点值的数交换交换这两个数反转后缀将拐点之后的子数组反转使其变为最小升序若找不到拐点说明已是最大排列直接反转整个数组。implSolution{pubfnnext_permutation(nums:mutVeci32){letnnums.len();ifn2{return;}// Step 1: 从右向左找第一个升序对 nums[i-1] nums[i]// i 最终指向拐点右侧的起始位置letmutin-1;whilei0nums[i-1]nums[i]{i-1;}// Step 2 3: 如果找到了拐点从右找第一个大于 nums[i-1] 的数并交换ifi0{letmutjn-1;whilej0nums[j]nums[i-1]{j-1;}nums.swap(i-1,j);}// Step 4: 反转 i 到末尾的子数组// 若 i 0完全降序则反转整个数组nums[i..].reverse();}}执行流程图解以nums [1, 2, 7, 4, 3, 1]为例步骤 操作 数组状态初始 —[1, 2, 7, 4, 3, 1]Step 1 从右扫描1 3 4 7都降序直到2 7i 2指向 7 —Step 2 从右找第一个 nums[1]21, 3中3 2j 4—Step 3 交换nums[1]和nums[4]2 ↔ 3[1, 3, 7, 4, 2, 1]Step 4 反转nums[2..][7,4,2,1]→[1,2,4,7][1, 3, 1, 2, 4, 7]复杂度分析指标 复杂度 说明时间 O(n) 最多三次线性扫描 一次反转空间 O(1) 原地修改reverse()也是 O(1) 额外空间Rust 特有关键点避免下溢使用usize索引时若从n-2递减到-1会下溢。本实现让i从n-1开始通过nums[i-1] nums[i]判断循环条件i 0保证不会下溢。nums[i..].reverse()Rust 标准库直接提供切片反转原地操作且时间 O(k)、空间 O(1)比手写双指针交换更简洁。nums.swap(a, b)标准库提供的原地交换无需临时变量语义清晰。拐点定位最终i指向的是后缀的起始位置而非拐点本身。拐点是i-1这样设计使得最后反转区间统一为nums[i..]逻辑更干净。