31.下一个排列
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:]) }
