31. Next Permutation

math

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 and use only constant extra memory.

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

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:] 是最小升序排列，使整体排列最小化。

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()