下一个排列

暴力是把所有排列都列出来、排好序、找到当前这个的下一个。n 个数有 n 的阶乘种排列，光是 10 个数就三百多万种，直接超时。

高位不动、只动靠右的位，增幅才最小。所以我们从右往左找：第一个「还能往上抬一点」的位置。

第一步 · 从右往左找下降点 i：从最右边的 1 开始往左看。1 比 3 小？不，1 在 3 右边、比它小，继续。我们要找的是「左边比右边小」的那个台阶。

第一步 · 右段是纯递减，跳过：7、4、3、1 这一段从左到右是递减的，它本身已经是最大排法，动它只会变小。所以越过它，继续往左。

第一步 · 找到下降点 i=1（值 2）：走到下标 1，值是 2，它右边的 7 比它大。这就是下降点 i。我们要把这一位的 2 换成右边一个稍大的数。

第二步 · 右段里找「刚好大于 2」的数 j：现在盯住 i 右边这段。从最右的 1 开始往左找：1 比 2 大吗？不大，跳过。

第二步 · j 落在下标 4（值 3）：再往左是 3，比 2 大，停。因为右段是递减的，从右数第一个比 2 大的，正好就是「比 2 大但大得最少」的那个，它就是要换上高位的数。

第三步 · 交换 i 和 j（2 ↔ 3）：交换 i 和 j：2 和 3 互换。注意看下标 1 变成了 3、下标 4 变成了 2。前缀 1,3 已经比原来大，这一步保证了「确实变大」。

第四步 · 此时后缀仍是递减的：换完后，i 右边的 7,4,2,1 还是从大到小。前缀已经抬高了，尾巴就该取「最小」才整体最接近——但现在它是最大，得把它翻成最小。

第五步 · 反转后缀：双指针向中间靠（第 1 次）：用左右双指针反转后缀。l 在 2、r 在 5，交换两端：7 和 1 互换。后缀正从「最大」一步步翻成「最小」。

第五步 · 反转后缀：再向中间一步（第 2 次）：l 走到 3、r 走到 4，交换 4 和 2。再走一步两指针就相遇，反转结束。后缀变成 1,2,4,7，是这个前缀下最小的尾巴。

完成 · 得到下一个排列：结果出来了：[1,3,1,2,4,7]。高位被尽量靠右地抬高一格、尾巴换成升序最小，这就是字典序里紧挨着的下一个排列。

一句话本质：把尽量靠右的高位抬高最小的一格，再把它后面的尾巴翻成升序最小，整体就刚好大一点点。

雷区实演 · 已是最大排列 [3,2,1]：[3,2,1] 已经是最大排列。从右往左每一步都是「左大于右」，i 一直左移到越界。这时不交换，直接进第三步反转整段。

雷区实演 · 反转整段得回最小 [1,2,3]：因为 i+1 等于 0，第三步反转的是整个数组，[3,2,1] 翻成 [1,2,3]，正好是字典序最小的排列。这就是「最大变最小」的兜底分支。

面试追问：这四问围绕「为什么从右、为什么是最小的 j、为什么反转、最大怎么办」，把三步的道理讲透。

迁移阶梯：这套「找降点-换大数-翻后缀」是排列类的原子操作。会了它，再去看全排列 lc46 的回溯、以及康托展开求第 k 个排列，会顺很多。点开数组专题或问问小欧 AI 私教继续练。

边界三连：三个边界专打这题命门：单元素、已是最大、含重复值。写完先用它们自测一遍。