下一个排列。实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。
来自力扣31。
从右往左遍历，遇到降序停止。交换，反序。
时间复杂度：O(N)。
空间复杂度：O(1)。
代码用golang编写。代码如下：
package main
import (
"fmt"
)
func main() {
nums := []int{1, 3, 2}
nextPermutation(nums)
fmt.Println(nums)
}
func nextPermutation(nums []int) {
N := len(nums)
// 从右往左第一次降序的位置
firstLess := -1
for i := N - 2; i >= 0; i-- {
if nums[i] < nums[i+1] {
firstLess = i
break
}
}
if firstLess < 0 {
reverse(nums, 0, N-1)
} else {
rightClosestMore := -1
// 找最靠右的、同时比nums[firstLess]大的数，位置在哪
// 这里其实也可以用二分优化，但是这种优化无关紧要了
for i := N - 1; i > firstLess; i-- {
if nums[i] > nums[firstLess] {
rightClosestMore = i
break
}
}
//swap(nums, firstLess, rightClosestMore);
nums[firstLess], nums[rightClosestMore] = nums[rightClosestMore], nums[firstLess]
reverse(nums, firstLess+1, N-1)
}
}
func reverse(nums []int, L, R int) {
for L < R {
nums[L], nums[R] = nums[R], nums[L]
L++
R--
}
}执行结果如下：
