Leetcode 31. 下一个排列

心路历程：

第一眼没看出来该怎么去做，主要没看懂题意里什么是字典序，后来从它的例子里看出其实相当于把这些数排列起来组成的数字最大，因此越靠近0位置的数字越影响整个大小。
看到O(1)的空间复杂度要求，基本上意味着得原地操作数组，双指针没跑了。需要注意遍历顺序是从后往前找数组的第一个递减元素，并找到该元素之后第一个比他的元素交换，然后在对第一个递减元素后面的所有元素进行递增排序。

注意的点：

1、许久没写冒泡排序，一下子忘了冒泡排序的第二层指针才是交换元素的指针，第一层只代表遍历顺序。
2、注意冒泡排序时需要从指定位置开始而不是0位置
3、双指针时注意判断条件

解法：反向先后双指针 +冒泡排序

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 双指针
        n = len(nums)
        if n == 1:
            return
        f, s = n-1, n-1
        while f -1 >= 0 and nums[f-1] >= nums[f]: # 找到反向降低的第一数（正向递减）
            f = f - 1
        if f == 0:  # 证明到头了也没找到反向递减的数，说明此时数最大了已经
            start = 0
        else:  # 说明找到了递减的数
            f = f - 1
            while nums[s] <= nums[f]: s -= 1
            nums[f], nums[s] = nums[s], nums[f]
            start = f + 1
        # 将[f+1:]后面的数据正向递增，相当于对f+1后面的进行冒泡排序or将当前s指向的位置插入后再逆序
        for j in range(n-1-start):
            c = 0
            for i in range(start, n-1-j, 1):
                if nums[i] > nums[i+1]:
                    nums[i], nums[i+1] = nums[i+1], nums[i]
                    c += 1
            if c == 0: break