点击获取AI摘要

1432. 改变一个整数能得到的最大差值 M

给你一个整数 num 。你可以对它进行以下步骤共计两次：

选择一个数字 x (0 <= x <= 9).
选择另一个数字 y (0 <= y <= 9) 。数字 y 可以等于 x 。
将 num 中所有出现 x 的数位都用 y 替换。

令两次对 num 的操作得到的结果分别为 a 和 b 。

请你返回 a 和 b 的 最大差值 。

注意，新的整数（a 或 b）必须不能 含有前导 0，并且非 0。

示例 1：

输入：num = 555
输出：888
解释：第一次选择 x = 5 且 y = 9 ，并把得到的新数字保存在 a 中。
第二次选择 x = 5 且 y = 1 ，并把得到的新数字保存在 b 中。
现在，我们有 a = 999 和 b = 111 ，最大差值为 888

示例 2：

输入：num = 9
输出：8
解释：第一次选择 x = 9 且 y = 9 ，并把得到的新数字保存在 a 中。
第二次选择 x = 9 且 y = 1 ，并把得到的新数字保存在 b 中。
现在，我们有 a = 9 和 b = 1 ，最大差值为 8

示例 3：

输入：num = 123456
输出：820000

示例 4：

输入：num = 10000
输出：80000

示例 5：

输入：num = 9288
输出：8700

提示：

1 <= num <= 10⁸

问题分析

给定一个正整数 num，允许对其进行两次“全局替换”操作，每次操作选择数字 x（0–9）和 y（0–9），将 num 的所有 x 位替换为 y，得到两个新数 a 和 b。要求最大化差值

$\max Diff = a - b$

且替换后生成的数不能有前导 0。

关键在于：

第一次操作要尽可能让 a 最大。
第二次操作要尽可能让 b 最小。

算法思路

构造最大值 $a$
- 将 num 转为字符串 s。
- 从左往右找到第一个字符不为 '9' 的位置，其字符记为 $x_{\max}$ 。
- 若存在，则把所有等于 $x_{\max}$ 的字符替换为 '9'，得到字符串 s_a，转换为整数即为 $a$ ；否则 $a = \text{num}$ 。
构造最小值 $b$
- 先将 $b$ 初始化为原数 num。
- 若 s[0] != '1'，则取首字符 $x_{\min}=s[0]$ ，将所有等于它的字符替换为 '1'，得到 s_b，转为整数即为 $b$ 。
- 否则（首位已是 '1'），从 s[1:] 中找到第一个既不是 '0' 也不是 '1' 的字符，记作 $x_{\min}$ $x_{m i n}$ 。
  - 若找到，将所有等于它的字符替换为 '0'，得到 s_b，转为整数即为 $b$ 。
  - 若遍历完未找到，则保持 $b=\text{num}$ 。
返回差值

$\max Diff = a - b.$

时间复杂度

字符串长度 $d$ （即数字位数，最大 9 位）。
构造 $a$ 需一次线性扫描与一次替换： $O(d)$ 。
构造 $b$ 同样为一次扫描与一次替换： $O(d)$ 。
整体时间复杂度：

$O(d)$
空间复杂度： $O(d)$ 用于存储中间字符串。

代码分解

初始化
- s = str(num)
- a = num, b = num

构造 $a$

for ch in s:
    if ch != '9':
        x_max = ch
        a = int(s.replace(x_max, '9'))
        break

构造 $b$

if s[0] != '1':
    x_min = s[0]
    b = int(s.replace(x_min, '1'))
else:
    for ch in s[1:]:
        if ch not in ('0', '1'):
            x_min = ch
            b = int(s.replace(x_min, '0'))
            break
    # 若未 break，则 b 保持 num

代码实现

class Solution:
    def maxDiff(self, num: int) -> int:
        s = str(num)
        # 初始化
        a, b = num, num

        # 构造最大值 a
        for ch in s:
            if ch != '9':
                x_max = ch
                a = int(s.replace(x_max, '9'))
                break

        # 构造最小值 b
        if s[0] != '1':
            x_min = s[0]
            b = int(s.replace(x_min, '1'))
        else:
            for ch in s[1:]:
                if ch not in ('0', '1'):
                    x_min = ch
                    b = int(s.replace(x_min, '0'))
                    break

        return a - b