中等

问题描述

给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。

注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。

示例 1：

输入：n = 12
输出：21

示例 2：

输入：n = 21
输出：-1

提示：

• 1 <= n <= 231 - 1

双指针

首先将数字转换成单个数字的数组，要找到下一个更大的数，需要从低位往高位开始即从数组尾部开始往前找到第一个递减的数字的位置 $i$，只要将这个位置的数字换成一个较大的数字，得到的数必然比当前的数要大。由于从位置 $i$ 开始，数组后面的数字都是非递减的，所以只需从数组最后一位往前找，找到某一个数，比 $i$ 位置上的数大，那么该数字就是比 $i$ 位置上的数大的数中最小的数，将其与 $i$ 位置上的数交换。此时得到的数必然比原来的数大，因为 $i$ 位置上的数字已经被换成了一个较大的数字。接下来只需将 $i$ 后面的数变成最小就可以了。显然 $i$ 后的数，从左到右是非递增的，因此，只需将 $i$ 后的数进行一次翻转，就可以得到最小的数。之后处理一下边界情况即可。

/**
 * @param {number} n
 * @return {number}
 */
var nextGreaterElement = function (n) {
  const nums = n
    .toString()
    .split('')
    .map((i) => +i)
  let i = nums.length - 2
  while (i >= 0 && nums[i] >= nums[i + 1]) i--
  if (i < 0) return -1
  let j = nums.length - 1
  while (j > i && nums[i] >= nums[j]) j--
  ;[nums[i], nums[j]] = [nums[j], nums[i]]
  i = i + 1
  j = nums.length - 1
  while (i < j) {
    ;[nums[i], nums[j]] = [nums[j], nums[i]]
    i++
    j--
  }
  const res = parseInt(nums.join(''))
  return res > Math.pow(2, 31) - 1 ? -1 : res
}

• 时间复杂度：$O(log\;n)$
• 空间复杂度：$O(n)$