下一个排列

力扣🔗：https://leetcode-cn.com/problems/next-permutation (opens new window)

题目

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

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

解题思路

• 首先从右往左遍历 nums，检查是否存在下一个更大的排列，依据是看能否找出相邻的两个数字，且满足前一数字小于后一个数字，即 nums[i] < num[i + 1]。如果找到满足该条件的情况，则表示存在下一个更大的排列，记录此时的索引 i（如果 i === -1，表示没有找到满足条件的情况）。·
• 然后从 nums 最后一数字开始向前寻找满足 nums[k] > nums[i] 的数字，直到 k === i + 1，接着替换这两个位置的数字。
• 最后，不管是否进行第二步操作，对 nums 第 i + 1 项起后面所有项进行反向排列，得到新的排列即是结果。

代码实现

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
function nextPermutation(nums) {
  debugger
  const l = nums.length
  if (l === 0) return nums

  let i = l - 2
  while (nums[i] >= nums[i + 1]) {
    // 从后往前寻找相邻的两个数，满足前一个数小于后一个数，记录前一个数的索引为 i
    i--
  }

  if (i >= 0) {
    // 如果找到满足 nums[i] < nums[i + 1] 的两数
    // 从后往前寻找比 nums[i] 小的数，找到后进行替换
    let k = l - 1
    while (k > i && nums[k] <= nums[i]) {
      k--
    }
    const temp = nums[k]
    nums[k] = nums[i]
    nums[i] = temp
  }

  // 反向排列索引 i 后的所有数字项（当 i === -1 时，所有项都会被排列）
  let left = i + 1
  let right = l - 1
  while (left < right) {
    const temp = nums[left]
    nums[left++] = nums[right]
    nums[right--] = temp
  }

  return nums
}