下一个排列（31）

题目

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

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

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

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。

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

算法

要找出当前数字的下一个大数，我们需要：

• 从后向前找到第一个i，i满足nums[i]<nums[i+1]，即[i+1, end)之前的所有数字呈递减排列
• 然后从后向前找到第一个k，k满足nums[k]>nums[i]，交换nums[i]和nums[k]，此时的[i+1, end)仍呈递减
• 翻转[i+1, end)，即让[i+1, end)呈递增
• 如果第一步中寻找i一直没有找到，说明整个数组呈递减，已经最大，此时直接翻转数组即可，即返回最小的字典

解释

• 第一步等于找到了需要进位的位置i
• 第二步等于进位了，且进位的位数是最小的可能
• 翻转相当于找到了进位后最小的一个数

var nextPermutation = function(nums) {
	if (nums.length <= 1) return nums;
	let last = nums.length - 1,
		exchange = nums.length - 1;
	while (last > 0 && nums[last] <= nums[last - 1]) {
		last--;
	}
	if (last > 0) {
		while (nums[exchange] <= nums[last - 1]) {
			exchange--;
		}
		[nums[last - 1], nums[exchange]] = [nums[exchange], nums[last - 1]];
	}
	nums.splice(nums.length, 0, ...nums.splice(last, exchange + 1).reverse());
	return nums;
};