LeetCode 题解工作台
改变一个整数能得到的最大差值
给你一个整数 num 。你可以对它进行以下步骤共计 两次 ： 选择一个数字 x (0 . 选择另一个数字 y (0 。数字 y 可以等于 x 。 将 num 中所有出现 x 的数位都用 y 替换。 令两次对 num 的操作得到的结果分别为 a 和 b 。 请你返回 a 和 b 的 最大差值 。 注意…
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
要想得到最大差值，那么我们应该拿到最大值与最小值，这样差值最大。 因此，我们先从高到低枚举 每个位置上的数，如果数字不为 `9`，就将所有该数字替换为 `9`，得到最大整数 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个整数 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^8
解题思路
方法一：贪心
要想得到最大差值，那么我们应该拿到最大值与最小值，这样差值最大。
因此，我们先从高到低枚举 每个位置上的数，如果数字不为 9，就将所有该数字替换为 9，得到最大整数 。
接下来，我们再从高到低枚举 每个位置上的数，首位不能为 0，因此如果首位不为 1，我们将其替换为 1；如果非首位，且数字不与首位相同，我们将其替换为 0，得到最大整数 。
答案为差值 。
时间复杂度 ，空间复杂度 。其中 为给定整数。
class Solution:
def maxDiff(self, num: int) -> int:
a, b = str(num), str(num)
for c in a:
if c != "9":
a = a.replace(c, "9")
break
if b[0] != "1":
b = b.replace(b[0], "1")
else:
for c in b[1:]:
if c not in "01":
b = b.replace(c, "0")
break
return int(a) - int(b)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(\log(\textit{num})) because the number of digits in num determines the operations. Space complexity is O(\log(\textit{num})) for storing the transformed strings of digits. |
| 空间 | O(\log (\textit{num})) |
面试官常问的追问
外企场景- question_mark
Check whether candidates correctly identify which digit to change to maximize and minimize independently.
- question_mark
Listen for mention of maintaining number validity while applying greedy choices.
- question_mark
Look for reasoning about why replacing all occurrences of a digit gives the largest difference efficiently.
常见陷阱
外企场景- error
Attempting to replace digits without considering leading zeros when minimizing.
- error
Overcomplicating by iterating through every possible digit replacement instead of greedy selection.
- error
Failing to apply the operation independently twice, leading to incorrect difference calculation.
进阶变体
外企场景- arrow_right_alt
Compute maximum difference if only a single replacement is allowed instead of two independent operations.
- arrow_right_alt
Allow negative integers and compute the maximum difference with the same greedy principle.
- arrow_right_alt
Restrict replacements to adjacent digits only and observe how greedy choices adapt.