31. 下一个排列

image.png

从数组的最右端开始扫描，找到从右向左递增的递增序列，158476531的数组序列，可以知道从右边往左边扫描的过程中发现13657是递增的序列，而到4的时候则不是递增的序列了，因为4大于了7，所以这个时候循环结束，循环变量记录了4这个位置，
在后面递增的序列中从右往左找到第一个比4大的位置可以知道是13657中的5对应的位置，这个时候需要将4的位置与5的位置进行互换，
因为调换元素之后那么剩下来的从左到右是递增的，所以需要进行翻转，应该是从4这个位置后面进行翻转，这样形成的数字序列才是下一个更大的排列

  1. func nextPermutation(nums []int) {
  2.     // 第一步从右往左查找最大的升序队列
  3.     i := len(nums)-2// 倒数第二个数
  4.     for i >= 0&&nums[i]>=nums[i+1] {
  5.         i--
  6.     }
  8.     if i==-1 {
  9.         // 从右往左一直是升序
  10.         sort.Ints(nums)
  11.     }else {
  12.         j := len(nums)-1
  13.         // 从右往左找第一个比i索引值大的数字索引坐标
  14.         for j>=0&&nums[j]<=nums[i]{
  15.             j--
  16.         }
  18.         //交换他两位置
  19.         nums[i], nums[j] = nums[j], nums[i]
  20.         // 重新排序
  21.         sort.Ints(nums[i+1:])
  23.     }
  24.     fmt.Println(nums)
  25. }
  27. func main() {
  28.     nextPermutation([]int{1,2,3})
  29.     nextPermutation([]int{3,2,1})
  30.     nextPermutation([]int{1,5,1})
  31.     nextPermutation([]int{1,1,5})
  32.     nextPermutation([]int{1,3,5,7,9})
  33. }

image.png