下一个排列

下一个排列的目标是什么？

• 求字典序中恰好比当前排列大的下一个排列;
• 不存在更大排列时 (降序) 重排为最小排列 (升序);
• 要求原地修改, 只用常数级额外空间;
• 基本思想: 从低位找一个较大的数去替换前面较小的数, 且增大的幅度尽量小;

下一个排列如何实现？

• 从右向左找第一个比右邻居小的元素 nums[i], 此时 [i+1, n-1] 必然降序;
• 从右向左找第一个大于 nums[i] 的元素 nums[j], 交换两者;
• 把 [i+1, n-1] 反转为升序, 使其成为最小后缀;
• 若不存在这样的 i, 整个数组降序, 直接反转全部即可;

function nextPermutation(nums: number[]): void {
  let i = nums.length - 2;
  while (i >= 0) {
    if (nums[i] < nums[i + 1]) break;
    i--;
  }

  if (i >= 0) {
    let j = nums.length - 1;
    while (j >= 0 && nums[j] <= nums[i]) j--;
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }

  let left = i + 1;
  let right = nums.length - 1;
  while (left < right) {
    [nums[left], nums[right]] = [nums[right], nums[left]];
    left++;
    right--;
  }
}

下一个排列的复杂度是多少？

• 时间复杂度: O(n), 三次线性扫描;
• 空间复杂度: O(1);