LeetCode-031反转后缀，如何构造？
摘要：本题在线练习：LeetCode 31. 下一个排列 - 在线练习（免费 · 无需登录 · AI 辅助）(https:onefly.topzero2Leetcodeplaygroun
本题在线练习：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 - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
# 2) find rightmost j with nums[j] > nums[i]
j = n - 1
while nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
# 3) reverse suffix i+1..end
l, r = i + 1, n - 1
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 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 交换
反转后缀得到最小后缀
掌握这三步，基本不会写错。