31. Next Permutation

Loading...LeetCode

60. Permutation Sequence

Q60 里提到的题，根据当前 permutation 来 in-place 做出下一个。做这个需要理解好 permutation 排序的性质：

1. 整个 ascending 的是最小的 permutation，最大的整个 descending，vice versa

2. permutation 中的子序列，也符合上一条性质，即整体 ascending 的子序列也已经是这个长度和元素构成下最小的。

具体解法见 https://leetcode.com/articles/next-permutation/，其实讲起来也很没意思，感觉没在考算法，在考 permutation 性质。

常规 straight forward 方法有一步是 reverse list slice, 在 python 里面写起来还挺 tricky，利用stack 的话可以规避这个操作，两份 code 都附着了。

straight forward

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i = len(nums)-1
        while i > 0:
            if nums[i-1] >= nums[i]:
                i -= 1
            else:
                pivot = i
                while pivot < len(nums)-1:
                    if nums[pivot+1] <= nums[i-1]: break
                    pivot += 1
                nums[i-1], nums[pivot] = nums[pivot], nums[i-1]
                nums[i:] = nums[i:][::-1] # 倒转list切片，这个值得记忆一下...
                break
                
        if i == 0:
            nums.reverse()

Stack

class Solution:
		def nextPermutation(self, nums: List[int]) -> None:
				"""
				Do not return anything, modify nums in-place instead.
				"""
				stack = []
				for i in range(len(nums) - 1, -2, -1):
						if i == -1:
								nums.reverse()
						elif (stack and stack[-1] <= nums[i]) or not stack:
								stack.append(nums[i])
						else:
								index = bisect.bisect_right(stack, nums[i])
								nums[i], stack[index] = stack[index], nums[i]
								for j in range(i + 1, len(nums)):
										nums[j] = stack[j - i - 1]
								break