31. 下一个排列

原始题目链接：https://leetcode-cn.com/problems/next-permutation/

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

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

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

解题思路：

题目要求给定的序列的字典序的下一个最大的序列，不存在的话就从小到大排列，即升序输出。首先查找给定的输入序列，从数组的最后面向前开始查找位置相邻并且大小上是升序的元素的位置（位置为二者较小的），找到满足条件的i后，然后从数组的最后面开始查找第一个比nums[i]大的元素，找到后（比如是第j位）互换i，j元素，最后为了保证是第一个大的字典序，将i位置后面的元素按照升序排列。具体实现看代码及注释。

class Solution:

    def swap(self, nums, i, j):
        """
        数组内元素互换位置
        """
        nums[i], nums[j] = nums[j], nums[i]
    
    def reverse(self, nums, index):
        """
        反转数组中指定位置到数组末尾的元素
        """
        start = index
        end = len(nums) - 1
        
        while end > start:
            self.swap(nums, start, end)
            start += 1
            end -= 1 

    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 + 1] <= nums[i]:
            i -= 1

        # 找到满足条件的i后，然后从数组的最后面开始查找第一个比nums[i]大的元素
        # 找到后（比如是第j位）互换i，j元素
        if i >= 0:
            j = len(nums) - 1
            while j >= 0 and nums[j] <= nums[i]:
                j -= 1
            
            self.swap(nums, i, j)
        
        # 为了保证是第一个大的字典序，将i位置后面的元素按照升序排列
        self.reverse(nums, i + 1)