难度: Medium
给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
示例 1 :
输入: 2736 输出: 7236 解释: 交换数字2和数字7。
示例 2 :
输入: 9973 输出: 9973 解释: 不需要交换。
注意:
- 给定数字的范围是 [0, 108]
Submission
运行时间: 15 ms
内存: 16.0 MB
class Solution:
def maximumSwap(self, num: int) -> int:
ans = num
s = list(str(num))
for i in range(len(s)):
for j in range(i):
s[i], s[j] = s[j], s[i]
ans = max(ans, int(''.join(s)))
s[i], s[j] = s[j], s[i]
return ans
Explain
这个题解采用了枚举法的思路。对于一个给定的数字，我们可以枚举所有可能的交换位置（即任意两个数字交换），然后比较交换后的数字大小，取其中最大的一个作为最终答案。具体实现时，先将数字转化为字符串，然后使用两重循环枚举所有交换的可能性，每次交换后都更新答案为当前最大值。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def maximumSwap(self, num: int) -> int:
ans = num
s = list(str(num)) # 将数字转化为字符串列表
for i in range(len(s)):
for j in range(i):
s[i], s[j] = s[j], s[i] # 交换 s[i] 和 s[j]
ans = max(ans, int(''.join(s))) # 更新答案为当前最大值
s[i], s[j] = s[j], s[i] # 恢复 s[i] 和 s[j] 的原始值
return ans # 返回最大的数字
Explore
在这个问题中，我们的目标是通过一次交换得到可能的最大数字。多次交换虽然可以探索更多可能性，但实际上一次精确的交换就足以达到最大化的目的。这是因为多次交换并不一定能进一步增大数字，而且会大幅增加算法的复杂度。因此，为了保持算法的效率和简洁性，只考虑一次交换是合理的。
题解中的内循环起始位置应该是从0开始，而不是从i开始。这是因为我们需要考虑当前位置i与之前所有位置j（j < i）的交换可能性。如果内循环从i开始，那么我们将无法考虑将i位置的数字与之前位置的数字交换的情况。这个错误可能是题解中的笔误。正确的做法应当是内循环从0到i-1，以确保能枚举所有可能的交换，从而找到最优解。
使用`max`函数来比较和更新最大值是这种枚举方法的一部分。尽管这种比较操作确实会增加执行时间，但在此算法框架下是必要的。每次交换后，使用`max`函数可以立即确定是否产生了一个更大的数字。然而，这种方法的效率主要受到两重循环的影响，因为时间复杂度为O(n^2)，其中n是数字的位数。在这种情况下，使用`max`函数的效率影响相对较小。
在每次交换后恢复数字到原始状态是为了确保每次交换都是独立的。这样做可以保证我们每次都是从未修改过的原始数字出发，独立考虑每种交换的结果。如果不恢复原始状态，那么后续的交换会在之前的交换基础上进行，这将导致无法正确评价单独一次交换的效果。此外，不恢复原始状态会使得问题复杂化，难以追踪每个交换的实际影响。