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 <= 108

解法思路

关键观察

要最大化数字，应该将左侧较小的数字与右侧最大的数字交换。具体步骤：

1. 从右向左遍历，记录每个位置右侧最大数字的值和索引。

2. 从左向右遍历，找到第一个比右侧最大值小的数字，进行交换。

算法步骤

1. 将数字转换为字符数组 digits 方便操作。

2. 初始化 max_idx 数组，max_idx[i] 表示 digits[i..n-1] 中最大数字的索引。

3. 从左到右扫描，找到第一个 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