> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/meta-2025/670.-maximum-swap.md).

# 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*.

 

**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
            
        




```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/meta-2025/670.-maximum-swap.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.