企业官网建设流程全解析

LeetCode 31. 下一个排列 — Python3 实现

核心思路

下一个排列的算法遵循字典序的排列规则，分为四步：

1. 找拐点：从右向左找到第一个左边小于右边的位置i（即nums[i] < nums[i+1]）
2. 找替换数：从右向左找到第一个大于nums[i]的数nums[j]
3. 交换：交换nums[i]和nums[j]
4. 反转后缀：将i+1到末尾的子数组反转（使其变为最小升序）

如果第 1 步找不到拐点，说明当前是最大排列（完全降序），直接反转整个数组得到最小排列。

classSolution:defnextPermutation(self,nums:list[int])->None:""" Do not return anything, modify nums in-place instead. """n=len(nums)# Step 1: 从右向左找第一个升序对 nums[i] < nums[i+1]# 找不到说明整个数组是降序，已经是最大排列i=n-2whilei>=0andnums[i]>=nums[i+1]:i-=1# Step 2: 如果找到了拐点，从右向左找第一个大于 nums[i] 的数ifi>=0:j=n-1whilej>=0andnums[j]<=nums[i]:j-=1# Step 3: 交换这两个数nums[i],nums[j]=nums[j],nums[i]# Step 4: 反转 i+1 到末尾的子数组# 如果 i < 0（没找到拐点），则反转整个数组left,right=i+1,n-1whileleft<right:nums[left],nums[right]=nums[right],nums[left]left+=1right-=1

执行流程图解

以nums = [1, 2, 7, 4, 3, 1]为例：

步骤 操作 数组状态
初始 —[1, 2, 7, 4, 3, 1]
Step 1 从右找拐点：7 > 4 > 3 > 1降序，直到2 < 7，i = 1—
Step 2 从右找第一个> 2的数：1, 3, 4都<= 2？不，3 > 2，j = 4—
Step 3 交换nums[1]和nums[4]：2 ↔ 3[1, 3, 7, 4, 2, 1]
Step 4 反转i+1到末尾：[7,4,2,1]→[1,2,4,7][1, 3, 1, 2, 4, 7]

复杂度分析

指标 复杂度 说明
时间 O(n) 最多遍历数组三次（找 i、找 j、反转），均为线性
空间 O(1) 原地修改，仅使用常数额外空间

关键细节

1. 为什么反转后缀就能得到最小升序？

   交换后，i+1到末尾仍然是降序的（因为 Step 2 找的是第一个大于nums[i]的数，其右侧都<= nums[i]且本身降序）。反转降序数组即可得到升序，也就是该后缀的最小排列。

2. 为什么 Step 2 从右边找？

   从右边找第一个大于nums[i]的数，能保证交换后增幅最小，从而得到紧邻的下一个排列。

3. i >= 0的判断

   如果i < 0，说明数组完全降序（如[3, 2, 1]），已经是最大排列。此时跳过交换，直接反转整个数组得到[1, 2, 3]（最小排列）。