---
description: "从右找第一个下降点 i，再从右找第一个比它大的数交换，最后把 i 之后的降序段反转成升序——增幅最小的那一步"
---

# 31. 下一个排列

LeetCode 31[^leetcode] · 中等 · 技巧

## 题

把整数数组 `nums` 原地改成字典序里紧挨着的下一个排列；已经是最大的（整体降序），就变回最小的（整体升序）。只能用常数额外空间。

例：`[1, 2, 3]` → `[1, 3, 2]`；`[3, 2, 1]` → `[1, 2, 3]`；`[1, 1, 5]` → `[1, 5, 1]`。

## 一句话

找最右边能变大的位置 `i`（`nums[i] < nums[i+1]`），把它换成右边比它大的数里最小的那个，再让右边变成最小——升序。

## 关键技巧

**要「变大」，且变得最少。** 字典序比大小看最左边不同的位置，所以想增幅最小，改动的位置要尽量**靠右**。

**第一步：找下降点。** 从右往左找第一个 `nums[i] < nums[i+1]` 的 `i`。`i` 右边是一段**非增**序列——它已经是这几个数能排出的最大排列，只动右边不可能变大，必须动 `i`。找不到 `i` 说明整体非增，已是最大排列。

**第二步：换一个刚好大一点的。** 在 `i` 右边找比 `nums[i]` 大的数里**最小**的那个。右段非增，所以从右往左第一个 `> nums[i]` 的 `j` 就是它。交换后 `nums[i]` 增幅最小。

**第三步：右边归零。** 交换后右段仍然非增（`nums[j]` 换成了更小的 `nums[i]`，但它仍 ≥ 右侧、< 左侧，顺序不破）。把它反转成非降序，就是最小的后缀——不用排序，反转即可，$O(n)$。

**整体降序时统一处理。** `i = -1` 时跳过交换，直接反转整段，最大排列变成最小排列。

## 解

```python
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        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
            nums[i], nums[j] = nums[j], nums[i]
        l, r = i + 1, n - 1                        # 右段反转成升序
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l, r = l + 1, r - 1
```

时间 $O(n)$，空间 $O(1)$。

## 延伸

- **生成全部排列**：[46. 全排列](0046-permutations.md) 用回溯；从最小排列反复调用本题也能按字典序生成全部，且天然去重（有重复元素时）。
- **第 k 个排列**（LeetCode 60）：康托展开，逐位按阶乘确定，不用一步步跳。
- **坑**：两处比较都要带等号（`>=`、`<=`），否则 `[1, 5, 1]`、`[1, 1]` 这类含重复的会出错或越界。

??? note "自测"

    ```python
    s = Solution()
    for arr, want in [
        ([1, 2, 3], [1, 3, 2]),
        ([3, 2, 1], [1, 2, 3]),
        ([1, 1, 5], [1, 5, 1]),
        ([1], [1]),
        ([1, 3, 2], [2, 1, 3]),
        ([1, 5, 1], [5, 1, 1]),
        ([2, 2], [2, 2]),
    ]:
        s.nextPermutation(arr)
        assert arr == want
    ```

[^leetcode]: [LeetCode 31](https://leetcode.cn/problems/next-permutation/)，2026-09-29 读。