670. Maximum Swap
string
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
解法思路
关键观察
要最大化数字,应该将左侧较小的数字与右侧最大的数字交换。具体步骤:
从右向左遍历,记录每个位置右侧最大数字的值和索引。
从左向右遍历,找到第一个比右侧最大值小的数字,进行交换。
算法步骤
将数字转换为字符数组
digits
方便操作。初始化
max_idx
数组,max_idx[i]
表示digits[i..n-1]
中最大数字的索引。从左到右扫描,找到第一个
digits[i] < digits[max_idx[i]]
的位置,交换两者。
时间复杂度: O(n)(两次遍历)
空间复杂度: O(n)(存储数字的字符数组和 max_idx
数组)
class Solution:
def maximumSwap(self, num: int) -> int:
digits = list(str(num))
n = len(digits)
max_idx = [0] *n
max_idx[-1] = n-1
for i in range(n-2, -1, -1):
if digits[i] > digits[max_idx[i+1]]:
max_idx[i] = i
else:
max_idx[i] = max_idx[i+1]
for i in range(n):
if digits[i] < digits[max_idx[i]]:
digits[i], digits[max_idx[i]] = digits[max_idx[i]], digits[i]
return int(''.join(digits))
return num
Last updated
Was this helpful?