实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

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

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

解法一：双指针交换

这题主要是要搞明白懂数学上的排列。分为四个步骤：

  1. Find nums[i] which is the first num ahead of the descending tail
  2. Find nums[j] which is the first num greater than nums[i] in the descending tail
  3. Swap nums[i] and nums[j]
  4. In-place reverse nums[i+1:] to make it ascending
    1. class Solution:
    2.  def nextPermutation(self, nums: List[int]) -> None:
    3.      # 1. find the first num before the descending tail
    4.      i = len(nums) - 2
    5.      while i >= 0 and nums[i] >= nums[i + 1]:
    6.          i -= 1
    7.      # 2. find the first num greater than nums[i] in the descending tail
    8.      if i >= 0:
    9.          j = len(nums) - 1
    10.          while j >= 0 and nums[i] >= nums[j]:
    11.              j -= 1
    12.          nums[i], nums[j] = nums[j], nums[i]
    13.      # 3. in-place reverse nums[i+1:] to make it ascending
    14.      left, right = i + 1, len(nums) - 1
    15.      while left < right:
    16.          nums[left], nums[right] = nums[right], nums[left]
    17.          left += 1
    18.          right -= 1