31. 下一個(gè)排列

實(shí)現(xiàn)獲取下一個(gè)排列的函數(shù)，算法需要將給定數(shù)字序列重新排列成字典序中下一個(gè)更大的排列。
如果不存在下一個(gè)更大的排列，則將數(shù)字重新排列成最小的排列（即升序排列）。
必須原地修改，只允許使用額外常數(shù)空間。
以下是一些例子，輸入位于左側(cè)列，其相應(yīng)輸出位于右側(cè)列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

思路

1. 這個(gè)題目主要是觀察, 找出當(dāng)前排列到下一個(gè)排列前后的變化

2. 分為三種情況考慮:

   1. 列表長度小于等于1
   2. 不存在更大序列, 即列表為降序排序
   3. 存在更大序列:
      • 從右往左遍歷, 找到第一個(gè)谷底的點(diǎn)
      • 找到谷底點(diǎn)后, 再從谷底的點(diǎn)開始往右遍歷, 找到剛好比谷底點(diǎn)大的那個(gè)點(diǎn)
      • 交換兩個(gè)點(diǎn)位置

      • 再將谷底點(diǎn)右側(cè)的點(diǎn)按升序排列(這樣值最小)

        
        
        列表[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):
            # 如果當(dāng)前點(diǎn)是谷底點(diǎn)
            if nums[i] > nums[i-1]:
                temp_i = i
                # 從谷底點(diǎn)開始從左往右找
                for j in range(i, len(nums)):
                    # 先比較是否比谷底的點(diǎn)大
                    if nums[j] > nums[i-1]:
                        # 再比較是否是更小的那個(gè)點(diǎn), 來找到那個(gè)剛好大于谷底點(diǎn)的點(diǎn)
                        if nums[temp_i] > nums[j]:
                            temp_i = j
                # 交換兩個(gè)點(diǎn)位置
                nums[i-1], nums[temp_i] = nums[temp_i], nums[i-1]  
                temp = nums[i:]
                temp.sort()
                nums[i:] = temp
                return

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