Leetcode 31. Next Permutation (python)

题目

解法

首先两个重要观察，对于一个序列来说，递减的序列一定是所有中最大的，而递增的序列一定是最小的。
所以要找到next permutation，我们应该从右遍往左边找，找打一个分界线，分界线右边是完全递减的序列。这样就可以知道，对分界线右边的数字做permutation不可能获得更大的值，也就意味着这个时候的next permutation应该是对对分界线左边的第一个值做改动，具体流程是这样的：

• 从现在序列的尾部往前找，找到第一个分界线，分界线右遍全部递减
• 将分界线右遍所有元素翻转，翻转后，分界线右边元素递增
• 从分界线开始往右边遍历，找到第一个比分界线左边第一个元素大的值，将这两个值交换得到next permutation
  注意一些边界情况的处理。然后这个流程对于有重复元素的情况也适用

class Solution:def nextPermutation(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""def reverse(left,right):while left<right:nums[left],nums[right] = nums[right],nums[left]left += 1right -= 1n = len(nums)left = 0for i in range(n-1,0,-1):if nums[i]>nums[i-1]:left = ibreakif left == 0:reverse(0,n-1)elif left == n-1:nums[n-1],nums[n-2] = nums[n-2],nums[n-1]else:reverse(left,n-1)temp = left-1while left<=n-1:if nums[left]>nums[temp]:nums[left],nums[temp] = nums[temp],nums[left]breakleft += 1