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

难度: Medium

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

选择一个数字 x (0 <= x <= 9).
选择另一个数字 y (0 <= y <= 9) 。数字 y 可以等于 x 。
将 num 中所有出现 x 的数位都用 y 替换。
得到的新的整数不能有前导 0 ，得到的新整数也不能是 0 。

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

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

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

Submission

运行时间: 24 ms

内存: 16.0 MB

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)

Explain

此题解的核心思路是通过两次替换操作生成两个整数a和b，然后计算它们的差值，以得到最大的差值。为了得到最大的a，应选择第一个非'9'的数字替换为'9'。而为了得到最小的b，首先检查首位数字是否为'1'。如果不是，将首位替换为'1'；如果首位已经是'1'，则找到第一个不是'0'或'1'的后续数字，将其替换为'0'。

时间复杂度: O(n)

空间复杂度: O(1)

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')  # 第一次修改：将第一个非'9'的字符替换为'9'
                break
        if b[0] != '1':
            b = b.replace(b[0], '1')  # 第二次修改：如果首位不是'1'，则替换为'1'
        else:
            for c in b[1:]:
                if c not in '01':
                    b = b.replace(c, '0')  # 如果首位是'1'，找到第一个非'0'或'1'的字符并替换为'0'
                    break
        return int(a) - int(b)  # 计算两次修改的数值差

Explore

将非'9'的数字替换为'9'是为了最大化整数的数值。'9'是单个数字中最大的，因此替换任何小于'9'的数字可以增加整数的值。这样的替换确保了得到的新数a尽可能大，从而最大化a和b的差值。

如果数字num的所有位都是'9'，那么对于生成最大数a的替换操作，实际上不会发生任何更改，因为没有低于'9'的数字可替换。在这种情况下，数a保持不变。对于最小数b的生成，如果首位也是'9'（即整个数字都是'9'），按照题解策略，首位'9'将被替换为'1'，使b尽可能小。计算差值时，使用修改后的b从未修改的a中减去。

当首位数字已经是'1'时，该位已经是可以取得的最小值，所以不需要更改。为了进一步减小整数的值，我们寻找后续位中第一个非'0'或'1'的数字，因为这些数字替换为'0'（最小的有效数字）可以最大程度地降低整数的值。这种策略旨在使b尽可能小，从而增大与a的差值。

在题解中，使用字符串的replace方法直接替换所有匹配的字符，不仅限于首次出现的字符。这意味着如果一个数字在num中出现多次，一旦决定替换该数字，将会替换num中的所有此数字。这种方法确保了一致性和简化的逻辑处理，但也可能导致在某些情况下替换更多的数字比预期的更早地达到最大或最小值。