LeetCode-Next Permutation

https://leetcode-cn.com/problems/next-permutation

最开始没看懂题意，后面才明白是去找全排列组合的下一个。

开始的思路是先把所有全排列写出来，然后再找，不过这样子太耗费时间，而且题目中也不允许（因为空间复杂度要求为线性）。

所以只能从找规律入手。看了半天，发现找到的规律比较零散，写起来比较困难。 然后就顺手看了一下网上的解法，真香.jpg。

主要思路是两次从后往前的查找。第一次是找到第一个非逆序排列的数字，第二次是找到刚好比第一次找到的数字大的数字，然后将这两个数字交换位置。接着，将第一次找到数字后的数字重新按照逆序排列即可。

这个规律太通用了，真香。

import "sort"
func nextPermutation(nums []int)  {
    n:=len(nums)
    i:=n-2
    j:=n-1
    for i>=0 && nums[i]>=nums[i+1]{
        i--
    }
    if i>=0{
        for nums[j]<=nums[i]{
            j--
        }
        nums[i],nums[j]=nums[j],nums[i]
    }
    sort.Ints(nums[i+1:])
}