31.下一个排列

下一个排列

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

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

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

示例 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. 从右向左找到第一个 nums[i] < nums[i+1] 的位置 i
2. 从右向左找到第一个 nums[j] > nums[i] 的位置 j
3. 交换 nums[i] 和 nums[j]
4. 将 i+1 到末尾的元素反转

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function (nums) {
  const n = nums.length;
  let i = n - 2;

  // 从右向左找第一个升序对
  while (i >= 0 && nums[i] >= nums[i + 1]) {
    i--;
  }

  if (i >= 0) {
    // 从右向左找第一个大于 nums[i] 的数
    let j = n - 1;
    while (j > i && nums[j] <= nums[i]) {
      j--;
    }
    // 交换
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }

  // 反转 i+1 到末尾
  let left = i + 1;
  let right = n - 1;
  while (left < right) {
    [nums[left], nums[right]] = [nums[right], nums[left]];
    left++;
    right--;
  }
};

该算法的关键在于理解字典序的规律：从右往左找到第一个”下降”的位置，然后在其右侧找到最小的比它大的数进行交换，最后反转右侧使其变为最小排列。时间复杂度 O(n)。