What is the main strategy for Maximum Swap?

The main strategy is to use a greedy approach: track the last occurrence of each digit and swap the first smaller digit with the largest digit appearing later.

Can we swap more than once in Maximum Swap?

No, the problem allows at most one swap. Swapping multiple times would require a different algorithm.

How do we handle numbers where swapping does not increase the value?

If no larger digit exists later for any position, the original number is already maximal and should be returned unchanged.

What are common mistakes in implementing Maximum Swap?

Common mistakes include swapping the first higher digit without checking rightmost occurrence or mismanaging indices when converting between string and integer.

How does the greedy choice plus invariant pattern apply here?

It ensures the leftmost digits are maximized first by swapping with the largest possible digit later, preserving the invariant that earlier digits are optimal.

#670

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

最大交换

给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。示例 1 : 输入: 2736 输出: 7236 解释: 交换数字2和数字7。示例 2 : 输入: 9973 输出: 9973 解释: 不需要交换。注意: 给定数字的范围是 [0, 10 8 ]

数学贪心

题目描述

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

示例 1 :

输入: 2736
输出: 7236
解释: 交换数字2和数字7。

示例 2 :

输入: 9973
输出: 9973
解释: 不需要交换。

注意:

给定数字的范围是 [0, 10⁸]

lightbulb

解题思路

方法一：贪心

我们先将数字转为字符串 $s$ ，然后从右往左遍历字符串 $s$ ，用数组或哈希表 $d$ 记录每个数字右侧的最大数字的位置（可以是数字本身的位置）。

接着从左到右遍历 $d$ ，如果 $s[i] \lt s[d[i]]$ ，则进行交换，并退出遍历的过程。

最后将字符串 $s$ 转为数字，即为答案。

时间复杂度 $O(\log M)$ ，空间复杂度 $O(\log M)$ 。其中 $M$ 是数字 $num$ 的取值范围。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def maximumSwap(self, num: int) -> int:
        s = list(str(num))
        n = len(s)
        d = list(range(n))
        for i in range(n - 2, -1, -1):
            if s[i] <= s[d[i + 1]]:
                d[i] = d[i + 1]
        for i, j in enumerate(d):
            if s[i] < s[j]:
                s[i], s[j] = s[j], s[i]
                break
        return int(''.join(s))

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
The candidate immediately recognizes that only one swap is allowed and aims for maximal leftmost digits.
question_mark
The candidate uses a mapping of last occurrences to efficiently identify swap opportunities.
question_mark
The candidate considers edge cases like numbers with descending digits or repeated maximum digits.

warning

常见陷阱

外企场景

error
Swapping the first higher digit without considering the rightmost occurrence may produce a suboptimal result.
error
Not handling numbers where no swap improves the result leads to incorrect output.
error
Confusing digit indices after converting between string and integer representation can cause off-by-one errors.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow multiple swaps to maximize the number, changing the problem from single-swap greedy to iterative maximization.
arrow_right_alt
Find the maximum number by swapping non-adjacent digits only, introducing additional positional constraints.
arrow_right_alt
Apply the same greedy swapping strategy to decimal or negative numbers, requiring careful handling of signs and decimal points.

help

常见问题

外企场景

继续练习

#738 单调递增的数字 #781 森林中的兔子 #910 最小差值 II