好的，我们来看 LeetCode 第 31 题「下一个排列」。

1. 题目描述

整数数组的一个 排列 就是将其所有成员以某种顺序排列。
例如，[1,2,3] 的排列按字典顺序依次为：
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]。

给定一个整数数组 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]

2. 理解“下一个排列”的意思

“下一个排列”指的是在字典序（数值顺序）上比当前排列大的最小排列。
例如对于 [1,2,3] 来说：

字典序排列：

1. [1,2,3]
2. [1,3,2]
3. [2,1,3]
4. [2,3,1]
5. [3,1,2]
6. [3,2,1]

如果当前是 [1,2,3]，下一个就是 [1,3,2]。
如果当前是 [3,2,1]，它是最大的，下一个就回到最小的 [1,2,3]。

3. 思路推导

我们要找比当前排列大的最小排列，应该尽量保持高位不变，只调整低位。

步骤推理：

1. 从右向左 找到第一个 相邻升序 对 (nums[i], nums[i+1])，即 nums[i] < nums[i+1]。
   此时 nums[i+1] 到末尾是 非递增（递减或相等）的。
   这个 i 就是需要交换的位置，因为从 i 向右看，右边部分已经是能组成的最大排列了，必须增大 nums[i]。

2. 如果找不到这样的 i（即整个数组是降序的），说明当前排列最大，直接反转整个数组得到最小排列。

3. 如果找到了 i，我们需要在 i 的右边部分（从 i+1 到末尾）找到一个比 nums[i] 大的 最小数（因为右边是降序的，所以从右向左找第一个大于 nums[i] 的数最合适）。

4. 交换 nums[i] 和找到的这个数。

5. 交换后，i 右边的部分仍然是降序的（因为原来右边是降序，且我们找到的是比 nums[i] 大的最小数，交换后右边部分仍然保持降序）。
   为了得到“紧挨着”的下一个排列，我们需要将 i 右边的部分变成升序（最小排列），直接反转即可（因为降序反转就是升序）。

4. 举例说明

以 nums = [1, 3, 5, 4, 2] 为例：

1. 从右向左找第一对升序：
   比较：2→4（降），4→5（降），5→3（升？不，5>3 是降），3→1（升？不，3>1 是降）——等一下，我们仔细来：
   从右向左：
   • 索引：4:2, 3:4 → 4>2? 降序
   • 索引：3:4, 2:5 → 4<5? 升序！所以 i=2（nums[2]=5, nums[3]=4 不对，检查一下：nums[2]=5, nums[3]=4，5>4 是降序，不是升序，继续往左）
   • 索引：2:5, 1:3 → 5>3 降序
   • 索引：1:3, 0:1 → 3>1 降序
     等等，我弄错了，重新严格来：

正确推导：
从右往左比较相邻：

• 2 和 4：2<4? 不，2<4 吗？2<4 是升序吗？不对，顺序是 nums[4]=2, nums[3]=4，比较 nums[3] 和 nums[4] 是 4 和 2，4>2 降序。
  比较 nums[2] 和 nums[3]：5 和 4，5>4 降序。
  比较 nums[1] 和 nums[2]：3 和 5，3<5 ✅ 升序！所以 i=1（nums[1]=3）。

2. 在 i=1 的右边部分 [5,4,2] 中从右向左找第一个大于 3 的数，找到 4（索引 3）。

3. 交换 nums[1] 和 nums[3]：数组变成 [1,4,5,3,2]。

4. 反转 i+1 到末尾（即反转 [5,3,2] 部分）：反转后是 [2,3,5]。
   最终数组：[1,4,2,3,5]。

检查字典序：
原 [1,3,5,4,2] 的下一个应该是 [1,4,2,3,5]，正确。

5. 算法步骤总结

1. 从右向左遍历，找到第一个满足 nums[i] < nums[i+1] 的索引 i。
2. 如果没找到（i == -1），反转整个数组，结束。
3. 从右向左，找到第一个大于 nums[i] 的数 nums[j]。
4. 交换 nums[i] 和 nums[j]。
5. 反转 i+1 到末尾的子数组。

6. 代码实现（思路对应）

def nextPermutation(nums):
    n = len(nums)
    i = n - 2
    while i >= 0 and nums[i] >= nums[i+1]:
        i -= 1
    
    if i >= 0:
        j = n - 1
        while j >= 0 and nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    
    # 反转 i+1 到末尾
    left, right = i+1, n-1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

7. 复杂度分析

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

这样，我们就完成了「下一个排列」的详细推理与实现。