31. 下一个排列

31. 下一个排列

1,6,9,8,7
第一步 查找从末尾开始需要保持升序，开始查找截断升序数字的索引 987 从末尾看一直是升序的 ，6是就截断
第二步 截断升序的索引和末尾开始升序数组中第一个比自己大数字交互位置 这个数组就是7 交换6和7的位置
第三步 对末尾开始升序数组进行重新排列，成一个整体数组的升序 现在17986 当时不是最合适的 需要转成17689

package main
import (
    "fmt"
    "sort"
)
func nextPermutation(nums []int){
    // 倒序查找第一个 默认是升序 查找截断升序的索引位置
    index :=-1
    for i:=len(nums)-1;i>0;i--{
        if nums[i-1]<nums[i] {
            index = i-1
            break
        }
    }
    // 从末尾一直是升序
    if index==-1 {
        sort.Ints(nums)
        return
    }
    for i:=len(nums)-1;i>index;i--{
        if nums[i]>nums[index] {
            nums[i],nums[index]=nums[index],nums[i]
            break
        }
    }
    sort.Ints(nums[index+1:])
    fmt.Println(nums)
}
func main() {
    nextPermutation([]int{1,2,3})//1 3 2
    nextPermutation([]int{3,2,1})// 1 2 3
    nextPermutation([]int{1,5,1})// 5 1 1
    nextPermutation([]int{1,1,5})// 1 5 1
    nextPermutation([]int{1,6,9,8,7})// 1 7 6 8 9
}