LeetCode 31. 下一个排列 — Python3 实现核心思路下一个排列的算法遵循字典序的排列规则分为四步找拐点从右向左找到第一个左边小于右边的位置i即nums[i] nums[i1]找替换数从右向左找到第一个大于nums[i]的数nums[j]交换交换nums[i]和nums[j]反转后缀将i1到末尾的子数组反转使其变为最小升序如果第 1 步找不到拐点说明当前是最大排列完全降序直接反转整个数组得到最小排列。classSolution:defnextPermutation(self,nums:list[int])-None: Do not return anything, modify nums in-place instead. nlen(nums)# Step 1: 从右向左找第一个升序对 nums[i] nums[i1]# 找不到说明整个数组是降序已经是最大排列in-2whilei0andnums[i]nums[i1]:i-1# Step 2: 如果找到了拐点从右向左找第一个大于 nums[i] 的数ifi0:jn-1whilej0andnums[j]nums[i]:j-1# Step 3: 交换这两个数nums[i],nums[j]nums[j],nums[i]# Step 4: 反转 i1 到末尾的子数组# 如果 i 0没找到拐点则反转整个数组left,righti1,n-1whileleftright:nums[left],nums[right]nums[right],nums[left]left1right-1执行流程图解以nums [1, 2, 7, 4, 3, 1]为例步骤 操作 数组状态初始 —[1, 2, 7, 4, 3, 1]Step 1 从右找拐点7 4 3 1降序直到2 7i 1—Step 2 从右找第一个 2的数1, 3, 4都 2不3 2j 4—Step 3 交换nums[1]和nums[4]2 ↔ 3[1, 3, 7, 4, 2, 1]Step 4 反转i1到末尾[7,4,2,1]→[1,2,4,7][1, 3, 1, 2, 4, 7]复杂度分析指标 复杂度 说明时间 O(n) 最多遍历数组三次找 i、找 j、反转均为线性空间 O(1) 原地修改仅使用常数额外空间关键细节为什么反转后缀就能得到最小升序交换后i1到末尾仍然是降序的因为 Step 2 找的是第一个大于nums[i]的数其右侧都 nums[i]且本身降序。反转降序数组即可得到升序也就是该后缀的最小排列。为什么 Step 2 从右边找从右边找第一个大于nums[i]的数能保证交换后增幅最小从而得到紧邻的下一个排列。i 0的判断如果i 0说明数组完全降序如[3, 2, 1]已经是最大排列。此时跳过交换直接反转整个数组得到[1, 2, 3]最小排列。