LeetCode每日一题: 31. 下一个排列

31. 下一个排列

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

思路

1. 这个题目主要是观察, 找出当前排列到下一个排列前后的变化

2. 分为三种情况考虑:

   1. 列表长度小于等于1
   2. 不存在更大序列, 即列表为降序排序
   3. 存在更大序列:
      • 从右往左遍历, 找到第一个谷底的点
      • 找到谷底点后, 再从谷底的点开始往右遍历, 找到刚好比谷底点大的那个点
      • 交换两个点位置

      • 再将谷底点右侧的点按升序排列(这样值最小)

        
        列表[1, 5, 8, 4, 7, 6, 5, 3, 1]的折线图

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 第一种情况, 啥也不用干
        if len(nums) <= 1:
            return
        
        # 第二种情况, 从右往左遍历列表
        for i in range(len(nums)-1, 0, -1):
            # 如果当前点是谷底点
            if nums[i] > nums[i-1]:
                temp_i = i
                # 从谷底点开始从左往右找
                for j in range(i, len(nums)):
                    # 先比较是否比谷底的点大
                    if nums[j] > nums[i-1]:
                        # 再比较是否是更小的那个点, 来找到那个刚好大于谷底点的点
                        if nums[temp_i] > nums[j]:
                            temp_i = j
                # 交换两个点位置
                nums[i-1], nums[temp_i] = nums[temp_i], nums[i-1]  
                temp = nums[i:]
                temp.sort()
                nums[i:] = temp
                return

        # 第三种情况, 直接按升序排列
        nums.sort()