一、题目简介

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。

1,2,3 → 1,3,2

3,2,1 → 1,2,3

1,1,5 → 1,5,1

地址：https://leetcode-cn.com/problems/next-permutation/

二、解法

1、解法1

func nextPermutation(nums []int)  {
   numsLen := len(nums)
   if numsLen <= 1{
       return 
   }

   var (
       frontIndex = numsLen -2
       backIndex = numsLen -1
   )

   for frontIndex >= 0{
       if nums[frontIndex] < nums[backIndex] {
          break
       }

        frontIndex --/*  */
        backIndex --        
   }

   if frontIndex >= 0 { 
       // 从front后面找一个比frontIndex大，且最下的元素插入frontIndex,剩下的元素倒排
       backIndex = numsLen -1
       for nums[frontIndex] >= nums[backIndex] {
           backIndex --
       }
    
        tmp := nums[frontIndex]
        nums[frontIndex] =  nums[backIndex]
        nums[backIndex] = tmp 

        frontIndex ++
   } else {
       frontIndex = 0
   }

   // 需要排序，从小到大
    backIndex = numsLen -1

    // 首尾交换
    for frontIndex < backIndex {
        tmp := nums[frontIndex]
        nums[frontIndex] =  nums[backIndex]
         nums[backIndex] = tmp

        frontIndex ++
        backIndex --
    }
}