31.下一个排列

/*
 * @lc app=leetcode.cn id=31 lang=typescript
 *
 * [31] 下一个排列
 */

// @lc code=start
/**
 Do not return anything, modify nums in-place instead.
 */
function nextPermutation(nums: number[]): void {
	/**
	 * 基本思想：从右向左找第一个不满足升序排列的元素，然后在其右侧找到第一个比它大的元素，并交换这两个元素，后将其进行逆序
	 */

	// 从右至左找第一个不满足升序排列的数组
	let r = nums.length - 1;
	let n: number = -1;
	let j: number = -1;
	while (r >= 0) {
		if (nums[r] > nums[r - 1]) {
			n = r - 1; // 从右向左找较小值：第一个不满足升序的数字
			break;
		}
		r--;
	}
	// 找到n后面数组第一个大于nums[n]的数字
	let index = nums.length - 1;
	while (index > n) {
		if (nums[index] > nums[n]) {
			j = index;
			break;
		}
		index--;
	}

	if (n == -1) {
        // 逆序整个数组
        nums.reverse()
	} else {
		// 交换
		[nums[n], nums[j]] = [nums[j], nums[n]];

		// n后面开始逆序
		nums.splice(n + 1, nums.length - n - 1, ...nums.slice(n + 1).reverse());
	}
	console.log(nums);
}

nextPermutation([3, 2, 1]);
// @lc code=end