670. 最大交换

🟠   🔖  贪心 数学  🔗 力扣 LeetCode

题目

You are given an integer num. You can swap two digits at most once to get the maximum valued number.

Return the maximum valued number you can get.

Example 1:

Input: num = 2736

Output: 7236

Explanation: Swap the number 2 and the number 7.

Example 2:

Input: num = 9973

Output: 9973

Explanation: No swap.

Constraints:

• 0 <= num <= 10^8

题目大意

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

示例 1 :

输入: 2736

输出: 7236

解释: 交换数字 2 和数字 7。

示例 2 :

输入: 9973

输出: 9973

解释: 不需要交换。

注意:

1. 给定数字的范围是 [0, 10^8]

解题思路

可以使用 贪心算法 来做这道题，希望通过交换两个数字，得到尽可能大的数字。自然想到，应该把数字序列中的某一位数字，和后面较大的数字交换。

关键点在于要 从右向左扫描，在这个过程中，记录每个数字的最大值及其位置。

同时，在从右往左的遍历的过程中，判断当前数字是否比最大数字小，如果是，则可以交换它们，记录交换对。

注意，除了当前数字，当前的最大数字也需要记录，因为后续遍历最大数字可能会更新。例如 num = 98368 时，应该是 3 和 8 交换，但是遍历结束时最大数字是 9。

遍历结束，如果找不到合适的交换对，说明当前数字已经是最大值，直接返回原数字。

复杂度分析

• 时间复杂度：O(n)，需要从右到左遍历数字字符串；
• 空间复杂度：O(n)，由于将数字转换为了字符串数组进行处理。

代码

/**
 * @param {number} num
 * @return {number}
 */
var maximumSwap = function (num) {
	const arr = num.toString().split(''),
		n = arr.length;
	let maxIdx = n - 1;
	let x = -1,
		y = -1;
	for (let i = n - 2; i >= 0; i--) {
		if (arr[i] > arr[maxIdx]) {
			// 更新从当前位置到末尾的最大数字索引
			maxIdx = i;
		} else if (arr[i] < arr[maxIdx]) {
			// 找到需要交换的两个位置
			x = i;
			y = maxIdx;
		}
	}
	// 如果没有可以交换的情况
	if (x == -1) return num;
	else {
		// 交换位置
		[arr[x], arr[y]] = [arr[y], arr[x]];
		return parseInt(arr.join(''));
	}
};

相关题目

题号	标题	题解	标签	难度
321	拼接最大数		栈 贪心 数组 2+