本题在线练习：LeetCode 31. 下一个排列 - 在线练习（免费 · 无需登录 · AI 辅助）(https://onefly.top/zero2Leetcode/playground.html?id=31)
配套刷题网站 Zero2Leetcode —— 内置本地 OJ + AI 教练，零门槛开始刷 Hot 100。
题目概述
给定一个整数数组 nums，将其重新排列成“字典序”下一个更大的排列。如果不存在更大的排列（已经是最大排列），则变成最小排列（升序）。
要求 原地修改，额外空间 O(1)。
核心思路：下一个排列只需要“动最右边能动的地方”
字典序的规则是：越靠左的位置越重要，想得到“刚好大一点”的排列，应该尽量让左侧保持不变，只在右侧做最小改动。
步骤（经典三步）：
- 从右往左找第一个位置
i，满足nums[i] < nums[i+1]，这叫“转折点/下降点”的前一个位置。 - 如果找到了
i，再从右往左找第一个j，满足nums[j] > nums[i]，交换nums[i]与nums[j]。 - 把
i+1到末尾这一段 反转（因为这一段原本是非递增的，反转后变成最小的升序后缀）。
如果第 1 步找不到 i，说明整个数组是非递增的，已经是最大排列，直接整体反转得到最小排列。
代码实现（原地）
class Solution:def nextPermutation(self, nums: list[int]) -> None:n = len(nums)# 1) find pivot: first i from right with nums[i] < nums[i+1]i = n - 2while i >= 0 and nums[i] >= nums[i + 1]:i -= 1if i >= 0:# 2) find rightmost j with nums[j] > nums[i]j = n - 1while nums[j] <= nums[i]:j -= 1nums[i], nums[j] = nums[j], nums[i]# 3) reverse suffix i+1..endl, r = i + 1, n - 1while l < r:nums[l], nums[r] = nums[r], nums[l]l += 1r -= 1
逐行拆解：为什么后缀要“反转”
在第 1 步找到的 i，意味着 i+1..end 这一段是 非递增 的：
... nums[i] < nums[i+1] >= nums[i+2] >= ... >= nums[n-1]
想让整体“刚好大一点”，把 nums[i] 换成后缀里“比它大一点点”的元素（第 2 步取最右的那个），然后让后缀变成最小可能（升序）。
由于后缀本来是非递增的，最省事的升序方式就是直接反转。
手动模拟：nums = [1,2,3]
- 找
i：2 < 3，所以i=1 - 找
j：从右找第一个>2的是 3，交换得到[1,3,2] - 反转后缀（位置 2 到末尾）不变
答案 [1,3,2]。
再看最大排列 [3,2,1]：
- 找不到
i（全程非递增） - 直接反转得到
[1,2,3]
复杂度分析
- 时间：
O(n)（最多三趟线性扫描/交换） - 空间：
O(1)
总结
下一个排列的关键是“最右侧最小改动”：
- 找转折点
i - 在右侧找最合适的
j交换 - 反转后缀得到最小后缀
掌握这三步，基本不会写错。