31. 下一个排列

解题思路

1. 从后往前找到第一个破坏单调递增性质的位置(x, y)
2. 将 array[x] 与 array[y, n) 中比 array[x] 大的最小的数字交换（注意是靠后的）
3. 将 array[y, n) 反过来
4. 别忘了特殊处理整个 array 本身就是单调递减的情况

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function (nums) {
  const len = nums.length
  if (len < 2) {
    return nums
  }
  const reversePart = (nums, begin) => {
    for (let i = begin, j = len - 1; i < j; i++, j--) {
      ;[nums[i], nums[j]] = [nums[j], nums[i]]
    }
  }
  outer: for (let i = len - 2; i >= 0; i--) {
    if (nums[i] < nums[i + 1]) {
      if (i + 1 === len - 1) {
        ;[nums[i], nums[i + 1]] = [nums[i + 1], nums[i]]
        break
      }
      for (let j = len - 1; j >= i; j--) {
        if (nums[i] < nums[j]) {
          ;[nums[i], nums[j]] = [nums[j], nums[i]]
          reversePart(nums, i + 1)
          break outer
        }
      }
    }
    if (i === 0) {
      nums.reverse()
    }
  }
  return nums
}