41. [中等] 下一个排列

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

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

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

示例 1：
```
输入：nums = [1,2,3]
输出：[1,3,2]
```

示例 2：
```
输入：nums = [3,2,1]
输出：[1,2,3]
```

示例 3：
```
输入：nums = [1,1,5]
输出：[1,5,1]
```

示例 4：
```
输入：nums = [1]
输出：[1]
```

>提示：
1 <= nums.length <= 100
0 <= nums[i] <= 100

# 代码参考

```go
package main

import "fmt"

// Next Seq
func main() {
	nums := []int{8, 4, 7, 6, 9, 3, 1, 5}
	num := []int{9, 8, 7, 6, 5, 4, 3, 2, 1}
	next_permutation(nums)
	next_permutation(num)
	fmt.Println(nums)
	fmt.Println(num)
}

func next_permutation(a []int) {

// 找到i-1 < i，证明i-1,n区间全部为降序
	j := 0
	for i := len(a) - 1; i > 0; i-- {
		if a[i-1] < a[i] {
			j = i - 1
			break
		}
	}

// 上个for循环没有找到符合的值，证明数组全部按降序排序
	// 直接反转并返回结果即可
	if j == 0 {
		reverse(a)
		return
	}

// 找到a[i] > a[j],互换
	for i := len(a) - 1; i > 0; i-- {
		if a[i] > a[j] {
			a[i], a[j] = a[j], a[i]
			break
		}
	}

// 反转剩余的部分，将降序改为升序
	reverse(a[j+1:])

}

// 反转：传入降序，改为升序
func reverse(a []int) {
	for i := 0; i < len(a)/2; i++ {
		a[i], a[len(a)-1-i] = a[len(a)-1-i], a[i]
	}
}
```

# 代码原理

**字典序**：可以将其理解为按照字典中单词的顺序进行排序。而由数字组成的字典序是指**数字按字典序要求从小到大的排序方式**。
例如，给定一个由数字组成的序列，可以将其视为一个数字组成的“单词”，然后按照字典中单词的排序规则对其进行排序。

题目要求我们实现一个函数，该函数接收一个由数字组成的列表（数字序列）作为输入，并将其重新排列为字典序中的下一个更大的排列。换句话说，我们需要找到给定数字序列的下一个比它大的排列，以满足字典序中的顺序。

以数字序列 [1,2,3] 为例，其排列按照字典序依次为：

```go
[1,2,3] --> [1,3,2] --> [2,1,3] --> [2,3,1] --> [3,1,2] --> [3,2,1]
```

即(数值按从左向右，从小到大排序)：

```go
123 < 132 < 213 < 231 < 312 < 321
```

这样，排列 [2,3,1] 的下一个排列即为 [3,1,2]。特别的，最大的排列 [3,2,1] 的下一个排列为最小的排列 [1,2,3]。

## 思路及解法

注意到下一个排列总是比当前排列要大，除非该排列已经是最大的排列。我们希望找到一种方法，能够找到一个大于当前序列的新序列，且变大的幅度尽可能小。具体地：

1. 我们需要将一个左边的「较小数」与一个右边的「较大数」交换，以能够让当前排列变大，从而得到下一个排列。

2. 同时我们要让这个「较小数」尽量靠右，而「较大数」尽可能小。当交换完成后，「较大数」右边的数需要按照升序重新排列。这样可以在保证新排列大于原来排列的情况下，使变大的幅度尽可能小。

以排列4,5,2,6,3,1为例:

- 我们能找到的符合条件的一对「较小数」与「较大数」的组合为2与3，满足「较小数」尽量靠右，而「较大数」尽可能小
- 当我们完成交换后排列变为4,5,3,6,2,1，此时我们可以重排「较小数」右边的序列，序列变为[4, 5, 3, 1, 2, 6]。

具体地，我们这样描述该算法，对于长度为n的排列a：

1. 首先从后向前查找第一个顺序对（i,i-1),满足a[i]\<a[i-1]。这样较小数即为a[i]。此时(i-1,n）必然是下降序列。

![](/media/202307/2023-07-22_130809_6436790.21843518008090512.png)

2. 如果找到了顺序对，那么在区间（i-1,n)中,从后向前查找第一个满足a[i]\<a[j]的元素j。这样较大数即为 a[j]。

![](/media/202307/2023-07-22_130834_6640270.21872196490765483.png)

3. 交换a[i]与a[j]，此时可以证明区间(i-1,n）必为降序。我们可以直接使用双指针反转区间(i-1,n)使其变为升序，而无需对该区间进行排序，

![](/media/202307/2023-07-22_130856_1811270.44833327474940954.png)

![](/media/202307/2023-07-22_130942_3776540.21375990053633664.png)

# 输出结果
```
[8 4 7 6 9 3 5 1]
[1 2 3 4 5 6 7 8 9]
```