题目

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2]。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。

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

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [1,1,5]
输出：[1,5,1]

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 100

思路

如果要求使用额外常数空间，那么空间换时间的路子基本就堵死了，不过好在这道题的思路并没有那么难想。我相信大家都能想到：

要找最靠后的升序序列，这样对于整体影响最小
但显然还不够，在此基础上，找到最后的一组升序序列时，应该再往后找找（此时后面一截一定是降序排列，不然就找不到这一组了），找一个最小的比这组升序序列中小数大的值跟它交换：

例如 [1，3，4，6，5，2]。最后的升序序列应该是4和6，但是再从6往后看看，其实用5和4交换其实影响更小，用2和4交换又会降低排列的字典序，所以应该选择用5和4交换

但还是不够，交换完成后，其实还需要看看交换后，升序序列中小数之后的这一节，是不是最小的，用不用再降低下字典序（因为前面的逻辑保障，其实交换后后面一截一定是降序）。

继续例如交换后为 [1，3，5，6，4，2]，此时显然，交换后字典序最小的应该是[1，3，5，2，4，6]，

所以最后就是，把交换之后，升序序列中小数位置之后的这一截再翻转下，变成升序。

至此，上代码。细节就放到代码注释了。

代码


func nextPermutation(nums []int) {
	// fmt.Printf("original: %v\n", nums)
	n := len(nums)
	i := n - 1
	for ; i > 0; i-- {
        // 从尾部找最靠后的升序序列
		if nums[i] > nums[i-1] {
            // 找比升序序列中小数字 大 的 最小数
			j := i
			for j < n && nums[j] > nums[i-1] {
				j++
			}
            // 交换
			nums[j-1], nums[i-1] = nums[i-1], nums[j-1]
			break
		}
	}

	k := n - 1
    // 看看用不用翻转
	if k > i {
        // 之前逻辑保证一定是降序，直接翻转就行
		for k > i {
			nums[i], nums[k] = nums[k], nums[i]
			i++
			k--
		}
	}
	//fmt.Printf("result: %v\n", nums)
}

半亩房顶

LeetCode-31. 下一个排列

题目

思路

代码

LeetCode-148. 排序链表