点击获取AI摘要

2566. 替换一个数字后的最大差值 E

给你一个整数 num 。你知道 Danny Mittal 会偷偷将 0 到 9 中的一个数字替换成另一个数字。

请你返回将 num 中 恰好一个 数字进行替换后，得到的最大值和最小值的差为多少。

注意：

当 Danny 将一个数字 d1 替换成另一个数字 d2 时，Danny 需要将 nums 中所有 d1 都替换成 d2 。
Danny 可以将一个数字替换成它自己，也就是说 num 可以不变。
Danny 可以将数字分别替换成两个不同的数字分别得到最大值和最小值。
替换后得到的数字可以包含前导 0 。
Danny Mittal 获得周赛 326 前 10 名，让我们恭喜他。

示例 1：

输入：num = 11891
输出：99009
解释：
为了得到最大值，我们将数字 1 替换成数字 9 ，得到 99899 。
为了得到最小值，我们将数字 1 替换成数字 0 ，得到 890 。
两个数字的差值为 99009 。

示例 2：

输入：num = 90
输出：99
解释：
可以得到的最大值是 99（将 0 替换成 9），最小值是 0（将 9 替换成 0）。
所以我们得到 99 。

提示：

1 <= num <= 10⁸

问题分析

给定一个正整数 num，Danny Mittal 可以选择一个数字 d1（0–9）并将所有出现的 d1 全局替换成另一个数字 d2（0–9）。

替换后可以包含前导零；
最大化操作和最小化操作可以使用不同的替换方案；
允许 d1 == d2（即不变）。
求在一次替换后得到的最大值与最小值之差。

算法思路

字符串化
将 num 转为字符串 s = str(num)，方便对每个字符全局替换。
枚举最大值
- 对于 s 中的每个不同字符 d，将 d → '9'，得到新字符串 s' = s.replace(d, '9')；
- 转为整数并取最大：
  
  $\mathrm{max\_val} = \max\bigl(\,\text{int}(s'),\;\text{当前最大值}\bigr).$
枚举最小值
- 对于 s 中的每个非零字符 d（跳过 d='0'），将 d → '0'，得到新字符串 s' = s.replace(d, '0')；
- 转为整数并取最小：
  
  $\mathrm{min\_val} = \min\bigl(\,\text{int}(s'),\;\text{当前最小值}\bigr).$
计算差值

$\text{答案} = \mathrm{max\_val} - \mathrm{min\_val}.$

时间复杂度

设数字位数为 $n$ ，不同字符数上限为 $k\le10$ 。
枚举每个字符时均进行一次字符串替换和整数转换，单次替换和转换为 $O(n)$ 。
总复杂度：

$O(k \cdot n) = O(n).$
空间复杂度：存储若干长度为 $n$ 的字符串，中间空间为 $O(n)$ 。

代码分解

初始化：

s = str(num)
orig = num
max_val = orig
min_val = orig

最大值枚举：

1
2
3

for d in set(s):
    s_max = s.replace(d, '9')
    max_val = max(max_val, int(s_max))

最小值枚举：

for d in set(s):
    if d == '0': 
        continue
    s_min = s.replace(d, '0')
    min_val = min(min_val, int(s_min))

返回结果：
1
return max_val - min_val

代码实现

class Solution:
    def minMaxDifference(self, num: int) -> int:
        s = str(num)
        orig = num
        max_val = orig
        min_val = orig

        # 枚举所有字符替换为 '9'，求最大值
        for d in set(s):
            s_max = s.replace(d, '9')
            max_val = max(max_val, int(s_max))

        # 枚举所有非 '0' 字符替换为 '0'，求最小值
        for d in set(s):
            if d == '0':
                continue
            s_min = s.replace(d, '0')
            min_val = min(min_val, int(s_min))

        return max_val - min_val