Skip to main content

31. Next Permutation

分析

从数字大小的角度来看是便捷的分析方式(但多位就不满足了 0 <= nums[i] <= 100 )
本质上应该从 dfs 和 选择的角度分析

1 3 2 5 4 作为例子
A
4 不具有下次一选择 需要回到上一层
5 依然如此
2 具有选择 4 / 5 选择空间 表现为 4 和 5 > 3,但这取决于以什么样的方式去选择

从右向左寻找 nums[i+1] 处于 nums [i] 的可选 空间的情况,在这题中表现为 nums[i+1] < num[i]
nums[i] 就是要进行交换的元素

下一步要思考与谁换
nums[i] 在可选空间中寻找下一个会选到的值 考虑到是非严格递增 因此 从最右向左边开始找 第一个大于就好

换过去后 [i+1, len-1] 仍然保持 非严格递增,换句话说,这就是基于 切换后的 nums[i] 最大的情况
我们要找的切换完后最小的情况,因此,反转[i+1, len-1]

题解

func nextPermutation(nums []int)  {
A := -1
for i := len(nums) - 2; i >= 0; i-- {
if nums[i] < nums[i + 1] {
A = i
break
}
}
if A != -1 {
for i := len(nums) - 1; i > A; i-- {
if nums[i] > nums[A] {
nums[i], nums[A] = nums[A], nums[i]
break
}
}
}
for i, j:= A + 1, len(nums) - 1; i < j; i, j = i + 1, j - 1 {
nums[i], nums[j] = nums[j], nums[i]
}
}