31.下一个排列

题解

题目：给一个数组，可以看出一个数字，求大于该数字并且最贴近该数字的数，特别的如果这个数是降序，则返回升序即可

思路：

变大的幅度尽可能小
1. 将一个左边的「较小数」与一个右边的「较大数」交换
2. 让这个「较小数」尽量靠右，而「较大数」尽可能小
3. 这样可以在保证新排列大于原来排列的情况下，使变大的幅度尽可能小

我们希望找到一个新序列，大于当前序列，并且变大的幅度尽可能的小
以4，5，2，6，3，1为例
从后向前找到第一个nums[i] < nums[i+1],这样[i+1,n]是降序 nums[i]为[较小数]---------2
[i+1,n]从后往前找第一个nums[j] > nums[i],称nums[j]为[较大数]---------3
交换nums[i]和nums[j],此时[i+1,n]还是降序
例子成为了4，5，3，6，2，1
将[i+1,n]升序-----4，5，3，1，2，6
答案就出来了

代码

func nextPermutation(nums []int) {
	i := len(nums) - 2
	j := len(nums) - 1
	//从后往前找相对小的数---[小数]
	for ; i >= 0; i-- {
		if nums[i] < nums[i+1] {
			break
		}
	}
	//此时[i+1,n]是降序

	//如果i=-1说明数组是降序排列，直接改成升序即可
	if i >= 0 {
		//从[i+1,n]中倒着找第一个大于 [小数] 的数---[大数]
		//为什么是第一个，因为这样较大数就尽可能小了
		for ; j >= i+1; j-- {
			if nums[i] < nums[j] {
				break
			}
		}
		//交换 大数 和 小数
		nums[i], nums[j] = nums[j], nums[i]
		//此时[i+1,n]还是降序
	}
	//将 大数 后面的所有升序
	sort.Ints(nums[i+1:])
}