---

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

• 标签：贪心、数学
• 难度：中等

题目链接

• 1432. 改变一个整数能得到的最大差值 - 力扣

题目大意

描述：给定一个整数 $num$，可以对其执行一次「替换」操作：选择两个数字 $x$ 和 $y$，将 $num$ 中所有数字 $x$ 替换为 $y$。不能有前导零（即替换后首位不能为 $0$）。

要求：返回一次替换能得到的最大值与最小值的差值。

说明：

• $1 \le num \le 10^8$。

示例：

• 示例 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

解题思路

思路 1：贪心

1. 核心思想

要得到最大值，将最高位且不是 $9$ 的数字替换成 $9$。
要得到最小值，将最高位且不是 $0$ 或 $1$ 的数字替换成 $0$（如果最高位不是 $1$）或换成 $1$（如果最高位不是 $1$ 则不能换 $0$）。

2. 具体步骤

第 1 步：将 $num$ 转为字符串 $s$。

第 2 步：找最大值：

遍历 $s$ 找第一个不是 '9' 的字符，将这种字符全部替换为 '9'。

第 3 步：找最小值：

• 如果第一个字符不是 '1'，将它（及其所有相同数字）替换为 '1'。
• 否则，遍历找第一个不是 '0' 也不是 '1' 的字符，将它替换为 '0'（注意不能替换首位）。

第 4 步：返回 $\max\_val - \min\_val$。

3. 举例说明

以 $num = 1234$ 为例：

最大值：$1$ 不是 $9$？$1$ 不是 $9$，将所有 $1$ 换成 $9$ → $9234$。
最小值：首位 $1$ 是 $1$，找第一个不是 $0$ 也不是 $1$ 的数字 → $2$，将 $2$ 换成 $0$ → $1034$。

差值：$9234 - 1034 = 8200$。

以 $num = 111$ 为例：

最大值：$1$ 不是 $9$，将所有 $1$ 换成 $9$ → $999$。
最小值：首位是 $1$，后面也是 $1$，无法再替换（所有数字都是 $1$），$111$。

差值：$999 - 111 = 888$。

思路 1：代码

class Solution:
    def maxDiff(self, num: int) -> int:
        s = str(num)

        # 求最大值
        max_str = s
        for ch in s:
            if ch != '9':
                max_str = s.replace(ch, '9')
                break

        # 求最小值
        min_str = s
        if s[0] != '1':
            min_str = s.replace(s[0], '1')
        else:
            for ch in s:
                if ch not in '01':
                    min_str = s.replace(ch, '0')
                    break

        return int(max_str) - int(min_str)

思路 1：复杂度分析

• 时间复杂度：$O(L)$，$L$ 是数字位数。
• 空间复杂度：$O(L)$。