题解 | #下一个排列#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型一维数组
#
class Solution:
    def nextPermutation(self , nums: List[int]) -> List[int]:
        # write code here
        if len(nums) <= 1:
            return nums

        # 从后往前找，找到不是按照从大到小排列的首个子串，假设子串开头位置为lind，则从lind+1位起，它是大到小排列
        lind = len(nums)-2
        while lind >= 0 and nums[lind] >= nums[lind+1]:
            lind -= 1

        # 如果lind < 0，则认为是最大排序结果，直接反转输出
        if lind < 0:
            nums.reverse()
            return nums

        # 从lind+1起，找到比lind位数据大的最小数，假设为rind
        rind = lind + 1
        while rind < len(nums) and nums[rind] > nums[lind]:
            rind += 1
        
        rind = rind - 1
        # 置换lind和rind的数据
        nums[lind], nums[rind] = nums[rind], nums[lind]

        # 将lind+1起的子串反转
        nums[lind+1:len(nums)].reverse()

        return nums