> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/meta-2025/31.-next-permutation.md).

# 31. Next Permutation

A **permutation** of an array of integers is an arrangement of its members into a sequence or linear order.

* For example, for `arr = [1,2,3]`, the following are all the permutations of `arr`: `[1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1]`.

The **next permutation** of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the **next permutation** of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

* For example, the next permutation of `arr = [1,2,3]` is `[1,3,2]`.
* Similarly, the next permutation of `arr = [2,3,1]` is `[3,1,2]`.
* While the next permutation of `arr = [3,2,1]` is `[1,2,3]` because `[3,2,1]` does not have a lexicographical larger rearrangement.

Given an array of integers `nums`, *find the next permutation of* `nums`.

The replacement must be [**in place**](http://en.wikipedia.org/wiki/In-place_algorithm) and use only constant extra memory.

 

**Example 1:**

<pre><code><strong>Input: nums = [1,2,3]
</strong><strong>Output: [1,3,2]
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [3,2,1]
</strong><strong>Output: [1,2,3]
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: nums = [1,1,5]
</strong><strong>Output: [1,5,1]
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= nums.length <= 100`
* `0 <= nums[i] <= 100`

分析

`记得数组切分时候，会建立一个新的数组，就不在原数组上做了`

**问题定义：**\
给定一个整数数组 `nums`，找到它的“下一个排列”（即字典序比当前排列大的最小排列）。如果当前排列已经是最大的排列（如 `[3,2,1]`），则返回最小的排列（即升序排列 `[1,2,3]`）。

***

#### **字典序（Lexicographical Order）**

* 类似于字符串的字典序，数字排列的字典序比较从左到右逐位比较：
  * `[1,2,3]` < `[1,3,2]` < `[2,1,3]` < `[2,3,1]` < `[3,1,2]` < `[3,2,1]`
* **下一个排列**：在所有可能的排列中，比当前排列大的最小排列。

***

#### **算法步骤**

1. **从后向前找第一个下降点（`nums[i] < nums[i+1]`）**
   * 目的是找到可以交换的最小高位。
   * 例如 `[1,5,8,4,7,6,5,3,1]`，第一个下降点是 `4`（`nums[3]`）。
2. **从后向前找第一个比 `nums[i]` 大的数（`nums[j] > nums[i]`）**
   * 目的是找到比 `nums[i]` 大的最小数交换。
   * 在上例中，`nums[6] = 5` 是第一个比 `4` 大的数。
3. **交换 `nums[i]` 和 `nums[j]`**
   * 交换后，`nums` 变成 `[1,5,8,5,7,6,4,3,1]`。
4. **反转 `i+1` 到末尾的部分**
   * 反转 `[7,6,4,3,1]` 得到 `[1,3,4,6,7]`。
   * 最终排列：`[1,5,8,5,1,3,4,6,7]`（比原排列大的最小排列）。

***

#### **为什么这样做？**

* **交换 `nums[i]` 和 `nums[j]`**：
  * 让高位尽可能小（`nums[i]` 换成稍大的 `nums[j]`）。
* **反转 `i+1` 到末尾**：
  * 确保 `nums[i+1:]` 是最小升序排列，使整体排列最小化。

<br>

```python3
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for i in range(len(nums) - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                for j in range(len(nums)-1, i,-1):
                    if nums[i] < nums[j]:
                        nums[i], nums[j] = nums[j], nums[i]
                        nums[i+1:] = nums[i+1:][::-1]
                        return
                    
        nums.reverse()
                
            

```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/meta-2025/31.-next-permutation.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.