https://leetcode-cn.com/problems/next-permutation/
https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-suan-fa-xiang-jie-si-lu-tui-dao-/

简介

组合出下一个更大的整数，
如输入 1，2，3；下一个比123更大的数是132；
比如[0,5,4,3,2,1]，下一个是[1,0,2,3,4,5]

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）
如输入：3，2，1；没有比321更大的排列，所以做升序排列即可：123

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

思路

下一个数比当前数大，只需要将后面的「大数」与前面的「小数」交换，就能得到一个更大的数。比如 123456，将 5 和 6 交换就能得到一个更大的数 123465。

我们还希望下一个数增加的幅度尽可能的小，这样才满足“下一个排列与当前排列紧邻“的要求。为了满足这个要求，我们需要：
1 在尽可能靠右的低位进行交换，需要从后向前查找
2 将一个尽可能小的「大数」与前面的「小数」交换。比如 123465，下一个排列应该把 5 和 4 交换而不是把 6 和 4 交换
3 将「大数」换到前面后，需要将「大数」后面的所有数重置为升序，升序排列就是最小的排列。以 123465 为例：首先按照上一步，交换 5 和 4，得到 123564；然后需要将 5 之后的数重置为升序，得到 123546。显然 123546 比 123564 更小，123546 就是 123465 的下一个排列

可视化算法过程

以求 12385764 的下一个排列 12386457 为例：

首先从后向前查找第一个相邻升序 的元素对 (i,j)，下标为： i=4，j=5；对应的值为 5，7

然后在 [j,end) 从后向前查找第一个大于 A[i] 的值 A[k]。这里 A[i] 是 5，故 A[k] 是 6：

将 A[i] 与 A[k] 交换。这里交换 5、6： 12386745

这时 [j,end) 必然是降序（因为从后向前第一个相邻升序 的元素对是 (i,j)，后面的元素肯定是降序的，在降序的元素中，从后向前，找第一个大于 A[i] 的值，两者交换，A[i]肯定比A[j]小，交换之后，依旧在降序的元素中）

逆置 [j,end)，使其升序。这里逆置 [7,5,4]：
因此，12385764 的下一个排列就是 1238 6 457。

最后再可视化地对比一下这两个相邻的排列（橙色是蓝色的下一个排列）：

算法过程

从后向前查找第一个相邻升序的元素对 (i,j)，满足 A[i] < A[j]。此时 [j,end) 必然是降序
在 [j,end) 从后向前查找第一个满足 A[i] < A[k] 的 k。A[i]、A[k] 分别就是上文所说的「小数」、「大数」
将 A[i] 与 A[k] 交换
可以断定这时 [j,end) 必然是降序，逆置 [j,end)，使其升序
如果在步骤 1 找不到符合的相邻元素对，说明当前 [begin,end) 为一个降序顺序，则直接跳到步骤 4

代码

力扣提交的代码
```go func nextPermutation(nums []int) { lenNums := len(nums) if lenNums <= 1 {
```
 return
```
}

// 定义初始值 i, j, k := lenNums-2, lenNums-1, lenNums-1

//从后往前，查找第一个升序元素对 for i >= 0 && nums[i] >= nums[j] {
```
 i--
 j--
```
}

//在j , end 倒叙元素中，从后往前查找第一个大于nums[i]的值nums[k]，并交换 if i >= 0 {
```
 for nums[i] >= nums[k] {
     k--
 }
 nums[i], nums[k] = nums[k], nums[i]
```
}

//逆序 j,end,使其升序 for i, j := j, lenNums-1; i < j; i, j = i + 1, j - 1 {
```
 nums[i], nums[j] = nums[j], nums[i]
```
}

}

<a name="NMiII"></a>
## 带详细注释
```go
package main

import "fmt"

func main() {
    nums := []int {1,7,3,4}  //申明切片且赋值
    nextPermutation( nums ) //切片是 引用传递
    fmt.Println(nums)
}

// 参数为nums,类型是切片int类型
func nextPermutation(nums []int) {

    lenNums := len(nums)
    if lenNums <= 1 {
        return
    }

    // 这里假设 i为倒数第二个数，j k 为最后一个数
    i, j, k := lenNums-2, lenNums-1, lenNums-1

    // 1 从后向前查找第一个相邻 升序 元素: A[i]<A[j]
    // 如果前面的比后面的大，说明是倒叙的，一直查，直到找到升序元对
    for i >= 0 && nums[i] >= nums[j] {
        i--
        j--
    }

    if i >= 0 { // 如果i小于0，说明没有升序的元素，跳过这个步骤：如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）
        // 2 从后向前查找第一个大于 A[i] 的值 A[k]，并交换
        // find: A[i] < A[k]
        for nums[i] >= nums[k] {
            k--
        }
        // 交换 A[i], A[k]
        nums[i], nums[k] = nums[k], nums[i]
    }

    // 3 将 A[j:end] 排列成升序的元素，由于之前是降序的，所以只需要头尾依次交换即可
    // 给i赋值j，也就是降序数组中最大的那个数
    // 给j赋值数组长度-1，也就是最后一个数
    // for循环条件为：i<j
    // 每次递增条件为：i++ j--
    // 如6 5 4 3 2 1，只需要将首位调换，下一次一个下标加1，一个减1，头尾每次向中间移动一步，然后将两个数调换，
    for i, j := j, lenNums-1; i < j; i, j = i + 1, j - 1 {
        nums[i], nums[j] = nums[j], nums[i]
    }
}

复杂度分许

时间复杂度：O(N)，其中 N 为给定序列的长度。
我们至多只需要扫描两次序列，（第一次是找升序元素对，第二次是交换i,k ）以及进行一次反转操作。

空间复杂度：O(1)，只需要常数的空间存放若干变量。

下一个排列

简介

思路

可视化算法过程

算法过程

代码

力扣提交的代码

复杂度分许