Array - 31. Next Permutation

1. Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

思路：

题目意思是找出一个比给定数组大的组合中最小的一个组合，比如比123大的组合当中最小的就是132，题目要求在原数组中操作，常数的空间复杂度，所以只能通过交换原数组的方式来实现。

1. 首先，可以明确的是一个数组，从小到大排序的组合一定是最小的，按从大到小排列的组合一定是组合中最大的。
2. 题目中规定了最极端的情况就是两个数组有序，那就直接翻转一下数组就可以得到结果，比如1 2 3 4 5翻转为5 4 3 2 1。
3. 如果一个数组无序，下一个最大的就取决于最后一段，是有极大值的拐点，还是极小值的拐点， 可以理解为升序代表最小，降序代表最大，先看极小值拐点的情况，这种情况直接把降序的两个点交换一下。至于有极大值点的那种情况，就在上升趋势中找出第一个比顶点小，和下降趋势比这个点大的做一下交换，就保证了上升趋势最小的性质，然后把后半部分的下降趋势翻转，就变成了代表最小的升序。而极小值的情况，可以看做是极大值的特殊情况，只不过下降趋势长度为零。

代码：

go：

func nextPermutation(nums []int)  {
    if nums == nil || len(nums) == 0 {
        return
    }
    
    size := len(nums)
    start := size - 2
    
    // 从后往前找，找到第一个比后一个小的位置
    for start >= 0  && nums[start] >= nums[start + 1] {
        start--
    }
    
    // 如果这个数不是递减，说明，需要和后面的第一个比他大的做一个调换
    if start >= 0 {
        // 找到第一个比当前数小的进行交换
        k := size -1
        for ; k > start && nums[k] <= nums[start]; {
             k--
        }
        nums[k], nums[start] = nums[start], nums[k]
    }
    
    // 这时候从start+1到数组结束是一个严格递减的数组，只用翻转一下，就会变成一个严格递增，也就是最小的数
    for i, j := start + 1, size - 1; i < j; {
        nums[i], nums[j] = nums[j], nums[i]
        i++
        j--
    }
}