Question

题目内容

解题思路

从低位挑一个大一点的数，交换前面一个小一点的数，变大的幅度要尽量小。

• [3, 2, 1]，没有下一个排列，已经稳定了，没法变大了。
• [1, 5, 2, 4, 3, 2]，从右往左，寻找第一个比右邻居小的数，把它换到后面去。
• 1 5 (2) 4 3 2，找到中间这个 (2)，接着还是从右往左找，找第一个比 2 大的数和它交换，交换后：1 5 (3) 4 (2) 2。
• 此时还没结束，变大的幅度还可以再小一点，千位变大了，后三位可以继续再小一点。
• 后三位肯定是递减的，翻转，变为 [1, 5, 3, 2, 2, 4]，即为所求。

代码实现

/**
 Do not return anything, modify nums in-place instead.
 */
const nextPermutation = (nums: number[]): void => {
  let i: number = nums.length - 2;
  while (i >= 0 && nums[i] >= nums[i + 1]) {
    i--;
  }
  if (i >= 0) {
    let j: number = nums.length - 1;
    while (j >= 0 && nums[j] <= nums[i]) {
      j--;
    }
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }
  let l: number = i + 1;
  let r: number = nums.length - 1;
  while (l < r) {
    [nums[l], nums[r]] = [nums[r], nums[l]];
    l++;
    r--;
  }
};