实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。
示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]
示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]
示例 4：
输入：nums = [1]
输出：[1]
提示：
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-permutation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一解
- 将“左边较小的数”与“右边较大的数”进行交换，使当前排列变大。
- ”较小数“尽量靠右，”较大数“尽可能小。交换完成后，”较大数“的右边数需要按照升序排列。
以 [4,5,2,6,3,1] 为例：
- 交换 2, 3 ，得到 [4,5,3,6,2,1] 。
- 将 3 右边的数升序排列 [4,5,3,1,2,6]。
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
# 找到比 nuns[i] 大的数
while j >= 0 and nums[j] <= nums[i]:
j -= 1
# 交换两个数
nums[i], nums[j] = nums[j], nums[i]
# 反转剩下的数
left, right = i + 1, len(nums) - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
- 时间复杂度 O(n) ：n 为数组长度。
- 空间复杂度 O(1)。