---
description: string
---

# 670. Maximum Swap

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_.

&#x20;

**Example 1:**

<pre><code><strong>Input: num = 2736
</strong><strong>Output: 7236
</strong><strong>Explanation: Swap the number 2 and the number 7.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: num = 9973
</strong><strong>Output: 9973
</strong><strong>Explanation: No swap.
</strong></code></pre>

&#x20;

**Constraints:**

* `0 <= num <= 10`<sup>`8`</sup>

#### **解法思路**

**关键观察**

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

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` 数组）



```python3
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
            
        




```
