1、題目描述

整數數組的一個?排列? 就是將其所有成員以序列或線性順序排列。

• 例如，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?的下一個排列。

必須?原地?修改，只允許使用額外常數空間。

示例 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、初始思路

2.1 思路

2.2 代碼

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