下一个排列
Next Permutation
把数组重新排列成字典序中恰好比当前排列大的下一个排列；如果不存在，就排成最小的排列。
在力扣中练习题目描述
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如，
arr = [1, 2, 3]，以下这些都可以视作arr的排列：[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
arr = [1, 2, 3]的下一个排列是[1, 3, 2]。arr = [2, 3, 1]的下一个排列是[3, 1, 2]。arr = [3, 2, 1]的下一个排列是[1, 2, 3]，因为[3, 2, 1]不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须 原地 修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3] 输出：[1,3,2]
示例 2：
输入：nums = [3,2,1] 输出：[1,2,3]
示例 3：
输入：nums = [1,1,5] 输出：[1,5,1]
提示：
1 <= nums.length <= 1000 <= nums[i] <= 100
解题思路
主解法
找拐点 · 交换后反转后缀
从右往左找第一个还能变大的位置
枚举所有排列再排序是 O(n!)，不可行。字典序的“下一个”要尽量保留前缀，只改动最靠右的一段。
从右往左找第一个满足 nums[i] < nums[i+1] 的位置 i。它右边的后缀一定是非递增的，已经处于“最大”状态；想让整个排列变大，必须动 i。
接着在后缀里找最靠右的、大于 nums[i] 的数 nums[j]，交换它们。这样前缀增加得最少。交换后后缀仍然递减，再把它反转成递增，就得到最小的后缀。
自拟主例 [1,3,5,4,2]：i 停在 3（3 < 5），后缀是 [5,4,2]；最靠右的更大值是 4，交换得 [1,4,5,3,2]，反转后缀得 [1,4,2,3,5]。
图解
普通节点当前操作
分步图解
nums[3] = 4 是后缀里最靠右的更大值；交换 i 和 j。
- j
- 3
如果找不到 i（整个数组非递增），说明已经是最大排列，直接反转整个数组得到最小排列。时间 O(n)，空间 O(1)。
时间 O(n)空间 O(1)
易错点
- 找拐点时用 > 而不是 >=：重复元素会被当成拐点，下一个排列算错。
- 找 j 时用 >= 而不是 >：会交换到相等元素，前缀没有真正变大。
- 反转整个数组而不是 i 之后的后缀：前缀被破坏，得到错误的排列。
- i = -1 时仍访问 nums[i]：需要先判断再交换，最后统一反转 i+1 开始的后缀。
代码与演示
演示输入
nums = [1,3,5,4,2]i 从倒数第二个位置开始：先找“右边已经递减”的最长后缀。
- i
- 3
查看 C++ 代码
延伸阅读
- C++ 的 std::next_permutation 就是这套逻辑；理解它可以解释为什么重复元素也不会漏掉排列。
- 上一个排列是对称的：找第一个 nums[i] > nums[i+1]，再找最靠右的较小值，交换后反转后缀。