031._next_permutation.md

###31. Next Permutation

题目: https://leetcode.com/problems/next-permutation/

难度:

Medium

参照wikipedia：

https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

看一个permutation，比如

125430

• 从末尾开始，找到decreasing subsequence，5430，因为来调5430无论怎么调，都不可能有比它更小的，数也被自然的分成两部分(1,2) 和 （5，4，3，0)
• 下一步是找这个sequence里面第一个比前面部分，比2大的，3，也很容易理解，因为下一个必定是(1,3)打头
• 交换 3和2 ，变成 (1,3,5,4,2,0),再把后面的部分reverse，得到后面部分可得到的最小的

这个时候，得到下一个sequence 130245

这道题其实一点也不容易写对，需要考虑很多状况，比如这里说的decreasing subsequence，比如一定要到比前面大的，所以一定要弄明白大于号小于号的使用。

比如 [5, 1, 3, 2, 1, 1]

我们就首先需要找到 5 之后的 1， 然后再找到从后往前数比1大的2，再完成交换，最后完成reverse

 5 1 3 2 1 1
   ↑
5 1 3 2 1 1
  ↑   ↑

5 2 3 1 1 1

5 2 1 1 1 3

还需要考虑的特殊情况包括： [3, 2, 1] 没有更小的，就用 [1, 2, 3], 而这种情况我们的 m 和 n 会直接都是0，我们就直接进入reverse阶段。

AC 代码

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        m, n = 0, 0
        for i in range(len(nums) - 2, 0 , -1):
        	if nums[i] < nums[i+1]:
        		m = i 
        		break

        for i in range(len(nums) - 1, 0 , -1):
        	if nums[i] > nums[m]:
        		n = i
        		break

        if m < n :
        	nums[m], nums[n] = nums[n], nums[m]
        	nums[m+1:] = nums[len(nums):m:-1] # nums[m+1:][::-1]
        else:
        	nums = nums.reverse()

可以注意的是我们的Python reverse有众多选项，比如我们的 .reverse 是直接mutate list，还有 a[::-1]，还有比如这种，根据so，最高效的应该是Best way to create a “reversed” list in Python? [::-1]

>>> seqRange = range(5, 9)
>>> print(list(reversed(seqRange)))