好的，我们这次来详细讲解 LeetCode 第 31 题“下一个排列”。

一、题目描述

题目链接：LeetCode 31. 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 = [3,2,1] 的下一个排列是 [1,2,3]（因为没有更大的排列，所以返回最小排列）
• arr = [1,1,5] 的下一个排列是 [1,5,1]

要求

• 必须 原地 修改，只允许使用额外常数空间。

二、理解“下一个排列”的字典序规则

字典序（lexicographical order）就是像字典那样排序：
比较两个序列时，从第一个元素开始比，如果相同就比较下一个，直到某个位置的元素不同，该位置元素较小的序列排在前面。

例子：
[1,2,3] < [1,3,2] < [2,1,3] < [2,3,1] < [3,1,2] < [3,2,1]

我们要找的是：给定排列，找出在字典序中紧挨着它的、比它大的排列。

三、推导算法思路（循序渐进）

1. 观察规律

假设数组是 [1,5,8,4,7,6,5,3,1]，我们要找它的下一个排列。

步骤 1：从右往左找第一个下降的位置
从右往左遍历，找到第一个满足 nums[i] < nums[i+1] 的索引 i。

• 为什么？因为如果从右往左一直是升序（即从右往左看是降序），那么这部分已经是这部分数字能组成的最大排列，必须改动更左边的数字。

例子：
1 5 8 4 7 6 5 3 1
从右往左：1, 3, 5, 6, 7, 4, 8, 5, 1
比较相邻：
1<3? 是，但我们要找 nums[i] < nums[i+1]，从右往左看相邻对：
... 4 和 7：4 < 7，找到！
所以 i = 3（0-based 索引，nums[3] = 4）。

此时 nums[i+1:] 是降序排列 [7,6,5,3,1]。

步骤 2：在 nums[i+1:] 中找到比 nums[i] 大的最小数字
因为 nums[i+1:] 是降序，所以从右往左找第一个大于 nums[i] 的数，就是比 4 大的最小数。
[7,6,5,3,1] 中，从右往左：1 不大于 4，3 不大于 4，5 大于 4，找到！
这个数的索引是 j = 5（nums[5] = 5）。

步骤 3：交换 nums[i] 和 nums[j]
交换后：[1,5,8,5,7,6,4,3,1]
注意：交换后 nums[i+1:] 仍然是降序（因为原来 nums[j-1] >= nums[j] > nums[i] 且 nums[j] 替换成较小的 nums[i] 后依然保持降序）。

步骤 4：将 nums[i+1:] 反转（变成升序）
反转 [7,6,4,3,1] 得到 [1,3,4,6,7]。
最终：[1,5,8,5,1,3,4,6,7]

为什么反转？
因为我们让 nums[i] 变大了一点，然后要让后面的部分尽可能小（即升序排列），这样才是紧挨着的下一个排列。

2. 边界情况

如果整个数组是降序的（比如 [3,2,1]），那么步骤 1 中找不到 i（i 会变成 -1），这时直接把整个数组反转得到最小排列 [1,2,3]。

四、算法步骤总结

1. 从右向左遍历，找到第一个索引 i 满足 nums[i] < nums[i+1]。如果找不到，直接跳到第 4 步。
2. 从右向左遍历（从末尾到 i+1），找到第一个索引 j 满足 nums[j] > nums[i]。
3. 交换 nums[i] 和 nums[j]。
4. 反转子数组 nums[i+1:]。

五、示例推导（用更小的例子）

例子：nums = [1,3,2]

1. 从右往左：2, 3, 1
   比较相邻：2>3? 否，3>1? 是，但我们要找 nums[i] < nums[i+1]：
   i=0：nums[0]=1 与 nums[1]=3：1<3 ✅，所以 i=0。

2. 在 i+1..end 即 [3,2] 中从右往左找第一个大于 nums[0]=1 的数：
   2>1 ✅，所以 j=2（nums[2]=2）。

3. 交换 nums[0] 与 nums[2]：得到 [2,3,1]。

4. 反转 nums[1:]（即 [3,1] 反转成 [1,3]）：得到 [2,1,3]。

检查字典序：[1,3,2] 的下一个排列确实是 [2,1,3]。

六、代码实现（Python）

def nextPermutation(nums):
    n = len(nums)
    # 步骤 1: 找第一个下降点 i
    i = n - 2
    while i >= 0 and nums[i] >= nums[i+1]:
        i -= 1
    
    if i >= 0:
        # 步骤 2: 在 i 右边找比 nums[i] 大的最小数
        j = n - 1
        while j > i and nums[j] <= nums[i]:
            j -= 1
        # 步骤 3: 交换
        nums[i], nums[j] = nums[j], nums[i]
    
    # 步骤 4: 反转 i+1 到末尾
    left, right = i+1, n-1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

七、复杂度分析

• 时间复杂度：O(n)，最多遍历数组两三次。
• 空间复杂度：O(1)，原地修改。

八、为什么这个算法是正确的？

核心思想：

• 我们要得到比当前排列大的最小排列，所以尽量保持左侧高位不变，只变动低位。
• 从右往左找第一个能变大的位置 i（即存在更大的排列）。
• 把 nums[i] 换成稍大一点的数（右边比它大的最小数）。
• 然后让 i 右边变成最小排列（升序），这样整体就是下一个排列。

这样讲解是否清晰？我们可以再通过一个例子手动模拟来加深理解。