leecode 31.下一个排列（Golang）
题目：
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
如何解决题目：
主要实现目标可以拆分为几点：
1.比之前要大
2.在比之前要大的基础上 ，要最小的那个
3.如果没有比之前更大的了， 比如 3->2->1 这样的倒序序列，则整体反转
实现步骤：
1.从后向前 查找第一个 相邻升序 的元素对 (i,j)，满足 A[i] < A[j]。此时 [j,end) 必然是降序
2.在 [j,end) 从后向前 查找第一个满足 A[i] < A[k] 的 k。A[i]、A[k] 分别就是上文所说的「小数」、「大数」
3.将 A[i] 与 A[k] 交换 //将最小的数 放到前面
4.可以断定这时 [j,end) 必然是降序，逆置 [j,end)，使其升序 //换的那个数 还是小于换之前的，所以依然是降序，要更小一点，所以反转
5.如果在步骤 1 找不到符合的相邻元素对，说明当前 [begin,end) 为一个降序顺序，则直接跳到步骤1
三、具体代码
func nextPermutation(nums []int) []int {length := len(nums)right := length - 1left := 0flag := false // 用来看是否找到了右边比左边大的值for right > left {if nums[right] > nums[right-1] { //低位的数字 大于高位的了，也就是找到了flag = true//从右开始找到第一个大于right-1的 ， 也就是找到最小的比 right-1大的值， 交换，交换完 右边还是降序，因为找的是第一个for i := length - 1; i >= right; i-- {if nums[i] > nums[right-1] {nums[i], nums[right-1] = nums[right-1], nums[i]break}}reverse(nums, right, length-1)break}right--}if !flag {reverse(nums, 0, length-1)}return nums}func reverse(nums []int, start, end int) {for start < end {nums[start], nums[end] = nums[end], nums[start]start++end--}}