编程面试：如何原地求下一个字典序排列？
面试官考察点
给定可能含重复值的整数数组，请原地改成字典序严格更大的下一个排列；若当前已经是最大排列，则改成升序的最小排列。
约束与边界
- 只能使用 O(1) 额外空间，允许交换和反转。
- 重复值不能被当成不同元素计数，但比较仍按数值进行。
- 数组为空或只有一个元素时，操作保持不变。
- 必须是全局字典序的下一个排列，不能只交换相邻元素。
找到最右侧拐点
从右向左找到第一个满足“左值严格小于右值”的位置 i。其右侧已经是非递增后缀；如果找不到拐点，整个数组降序，反转即可得到最小排列。
交换后再最小化后缀
有拐点时，从右向左找第一个大于 nums[i] 的元素 j。因为后缀非递增，首次找到的就是最小的可行更大值。交换 i 与 j，再反转 i + 1 之后的后缀，使变化幅度最小。
30 秒回答框架
“我从右找第一个上升拐点 i。若不存在，数组已是最大排列，直接反转。否则从右找第一个大于 nums[i] 的 j，交换两者，再把右侧后缀反转成升序。后缀原本非递增，所以这三步得到严格更大的最小候选，时间 O(n)、空间 O(1)。”
回答前需要澄清的问题
- 是否要求原地修改？若允许额外空间，可以排序复制；原地要求决定反转方案。
- “下一个”按数字升序还是字符串比较？负数和多位数时语义不同。
- 元素是否可能重复？重复值决定寻找严格大于而不是大于等于。
分步骤深入解答
设数组为 [1,2,3]，拐点是 1 的位置，交换后缀中最小的大于它的 2，得到 [2,1,3]，再反转后缀得到 [2,1,3]。对 [3,2,1] 找不到拐点，反转成 [1,2,3]。
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
j = n - 1
while nums[j] <= nums[i]:
j -= 1
swap(nums[i], nums[j])
reverse(nums, i + 1, n - 1)等值元素使用“大于等于”关系跳过拐点候选，使用“小于等于”关系跳过交换候选，保证变化严格增加。后缀反转而非排序，是因为拐点右侧已经有序，反转可在线性时间完成。
高质量示范回答
“字典序下一个排列要先让尽可能靠右的位置变大，同时让后缀尽可能小。我从右找最右的‘左值严格小于右值’拐点；从右找第一个大于它的值交换，随后反转后缀。没有拐点说明已是最大排列，反转整个数组。扫描、交换和反转都为 O(n)，只用常数变量。”
常见错误
- 从左找拐点，导致改变了更高位，跳过中间排列。
- 交换后直接结束，没有把后缀变成最小顺序。
- 用大于等于寻找交换值，重复值可能无法严格变大。
- 对后缀调用通用排序，空间或复杂度超出原地要求。
- 没有处理完全降序数组，返回原数组而不是最小排列。
错误表现与修正
对 [1,3,2] 若返回 [3,1,2]，说明拐点选得太靠左；正确结果是 [2,1,3]。对 [1,1,5] 若交换相等元素，说明严格比较边界错误。
生产化实现
封装一个只接收可变随机访问序列的函数，并让反转使用双指针。若元素类型可能溢出比较或跨语言比较规则不同，在接口层明确排序关系和异常输入策略。
验证清单
测试空数组、单元素、完全升序、完全降序、重复值、拐点在末端和多个最优排列。对小数组生成所有不重复排列，按字典序排序后逐个验证函数输出的下一个元素。
追问及应对
为什么一定要找最右拐点？
越靠右的拐点代表越小的高位变化；在它右侧寻找交换值并最小化后缀，才能得到当前排列之后的紧邻排列。
后缀为什么可以直接反转？
拐点是从右找到的，因此右侧原本非递增。交换一个更大值后，剩余后缀仍可通过反转恢复为升序最小状态。
如果要求第 k 个下一个排列呢？
重复执行会产生 O(k n) 时间；若 k 很大，可研究计数排列、跳跃或直接按排名解码，但需要额外的组合计数与重复值处理。
评分标准
- 拐点正确：从右寻找最右的严格上升位置。
- 交换正确：从右寻找第一个严格更大的值。
- 后缀正确：交换后反转为最小升序。
- 边界完整：覆盖降序、重复、空数组和单元素。
- 复杂度准确：O(n) 时间、O(1) 额外空间。
合规检查
确认三步算法、边界样例和复杂度结论在回答中保持一致。
面试作答要点
先解释“右侧最小变化”，再写拐点、交换和反转三步；用一个重复值例子说明严格比较，最后给出复杂度和全排列对拍。
一句话总结
下一个排列通过最右拐点、最小可行交换值和后缀反转，在原地 O(n) 时间得到字典序紧邻结果。