【LeetCode】0031 下一个排列

https://leetcode-cn.com/problems/next-permutation/

# -*- coding:utf-8 -*-
class Solution:
    def nextPermutation(self, nums):
        """
        Do not return anything, modify nums in-place instead.
        """
        firstIndex = -1
        n = len(nums)
        def reverse(nums, i, j):
            """
            翻转列表
            :param nums:
            :param i:
            :param j:
            :return:
            """
            while i < j:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j -= 1
        # 正序查找
        for i in range(n - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                firstIndex = i
                break
        # 查找不到直接翻转返回
        if firstIndex == -1:
            reverse(nums, 0, n - 1)
            return nums
        # 翻转查找
        secondIndex = -1
        for i in range(n - 1, firstIndex, -1):
            if nums[i] > nums[firstIndex]:
                secondIndex = i
                break
        # 交换两次查找的索引
        nums[firstIndex], nums[secondIndex] = nums[secondIndex], nums[firstIndex]
        # 翻转回来返回
        reverse(nums, firstIndex + 1, n - 1)
        return nums
if __name__ == '__main__':
    nums = [1, 2, 3]
    print(Solution().nextPermutation(nums))

思路：这道题，不得不说太巧了，太棒了，学到了很多。

这道题就是找比当前大的字典序，这道题的思路比较巧。

举个例子：[1,2,4,6,5,2,1]

首先从后向前找能够将当前字典序变大的位置，之所以是从后向前找，是因为要找对字典序影响最小的元素。我们找到了4，4之后的元素都是降序，也就是说对于4之后的元素，已经满足了最大字典序。

然后我们找到了影响字典序的罪魁祸首4，就要找他和谁交换呢？因为我们希望字典序的增加比较小，因此我们继续在4后倒序找比4大的数，因为4后已经满足降序，因此倒序找到比4大的数就是最小的数，也就是能影响字典序最小的数字5。

我们将4和5交换，此时列表变成 [1,2,5,6,4,2,1]

这时候5后依然保持着最大字典序的状态，我们将其翻转，到最小字典序。 [1,2,5,1,2,4,6]

这时候，因为5的改变， [1,2,5,1,2,4,6] 的字典序就是 [1,2,4,6,5,2,1] 的下一个。