Day22——排列

打卡题目：leetcode第31题，下一个排列
相似题目：60

【代码】

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # nums = [1, 2, 7, 4, 3, 1]
        first_index = -1
        second_index = -1
        # 先找到峰值前的第一个点的索引
        for i in range(len(nums)-2, -1, -1):
            if nums[i] < nums[i+1]:
                first_index = i
                break
        # 再找到峰值后的第一个大于峰值前的第一个点的索引
        for i in range(len(nums)-1, first_index, -1):
            if nums[i] > nums[first_index]:
                second_index = i
                break
        # 交换
        def reverse(nums, left, right):
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1
            return nums
        if first_index != -1:
            nums[first_index], nums[second_index] = nums[second_index], nums[first_index]
            nums = reverse(nums, first_index+1, len(nums)-1)
        else: # 说明全逆序
            nums = reverse(nums, 0, len(nums)-1)
        return nums