中等

问题描述

给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。

示例 1 :

输入: 2736
输出: 7236
解释: 交换数字 2 和数字 7。

示例 2 :

输入: 9973
输出: 9973
解释: 不需要交换。

提示：

• 给定数字的范围是 [0, 108]

贪心

尽可能让最大的数在最高位，于是从右向左遍历，设 $maxIdx$ 为当前遍历到的最大数字，若当前数字比 $nums[maxIdx]$ 更大，则更新 $maxIdx$ 的值，若比 $nums[maxIdx]$ 小，则记录当前边界 $[l, r]$，其中 $l$ 为当前遍历到的位置，$r$ 为当前记录到的 $maxIdx$。

/**
 * @param {number} num
 * @return {number}
 */
var maximumSwap = function (num) {
  const arr = num
    .toString()
    .split('')
    .map((v) => +v)
  const n = arr.length
  let maxIdx = n - 1
  let l = -1
  let r = -1
  for (let i = n - 1; i > -1; i--) {
    if (arr[i] > arr[maxIdx]) {
      maxIdx = i
    } else if (arr[i] < arr[maxIdx]) {
      l = i
      r = maxIdx
    }
  }
  if (l !== -1) {
    const tmp = arr[r]
    arr[r] = arr[l]
    arr[l] = tmp
    return +arr.join('')
  }
  return num
}

• 时间复杂度：$O(n)$，$n$ 为数字长度
• 空间复杂度：$O(n)$，$n$ 为数字长度