LeetCode热题100-下一个排列

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

• 例如，arr = [1,2,3]，以下这些都可以视作arr的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。

整数数组的下一个排列是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

• 例如，arr = [1,2,3]的下一个排列是[1,3,2]。
• 类似地，arr = [2,3,1]的下一个排列是[3,1,2]。
• 而arr = [3,2,1]的下一个排列是[1,2,3]，因为[3,2,1]不存在一个字典序更大的排列。

给你一个整数数组nums，找出nums的下一个排列。

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

首先理解下题：什么是下一个排列？

就是在所有比当前大的排列里，最小的那一个。比如：

• 当前是123
• 比它大的有：132、213、231…
• 最小的那个就是 132→ 所以123的下一个排列是132

明白这一点后就需要按照以下几步找：

核心思路（固定 4 步）

1. 从后往前找：第一个比后面小的数，记位置i
2. 再从后往前找：第一个比 nums [i] 大的数，记位置j
3. 交换 nums [i] 和 nums [j]
4. 把 i 后面的数字反转

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