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

难度: Easy

给你一个整数 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⁸

Submission

运行时间: 20 ms

内存: 16.1 MB

class Solution:
    def minMaxDifference(self, num: int) -> int:
        # 最大就是把最高的数换成9，如果已经是9了，同理往后推。如果其他位和最高位一样，也同样换成9.
        # 最小就是最高位换成0，剩下和上面同理
        # ss = str(num)
        # max_, min_ = ss,ss
        # max_flag,min_flag = True,True
        # max_va,min_va=-1,-1
        # max__replace=min__replace = num
        # for i in range(len(ss)):
        #     if ss[i] == ss[0] and min_flag:
        #         min_flag = False
        #         min_va = ss[i]
        #     if ss[i] != '9' and max_flag:
        #         max_flag = False
        #         max_va = ss[i]
        #     if max_flag == False and min_flag == False:
        #         break
        # if max_va != -1:
        #     max__replace = max_.replace(max_va, '9')
        # if min_va != -1:
        #     min__replace = min_.replace(min_va, '0')
        # return int(max__replace) - int(min__replace)
        
        #思路一样，更简洁的写法
        mx = num
        ss = str(num)
        for c in ss:
            if c != '9':
                mx = int(ss.replace(c, '9'))
                break
        return mx - int(ss.replace(ss[0],'0'))

Explain

为了解决问题，首先需要生成num的最大可能值和最小可能值。对于最大值，从num的最左侧开始，找到第一个不是'9'的数字，将其以及所有相同的数字都替换成'9'。这样可以确保得到最大的可能值。对于最小值，需要将num的最高位数字替换成'0'（如果最高位不是'0'的话），这样做可以得到最小的可能值。然后计算这两个值的差值，即为所求。该方法通过直接替换字符串中的字符来避免处理多次迭代和复杂的逻辑判断。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def minMaxDifference(self, num: int) -> int:
        # 转换整数为字符串
        ss = str(num)
        # 初始化最大值为原始数字
        mx = num
        # 遍历数字的每一个字符
        for c in ss:
            # 如果找到非'9'的字符，替换所有这个字符为'9'
            if c != '9':
                mx = int(ss.replace(c, '9'))
                break
        # 替换最高位的数字为'0'来得到最小值，然后计算两者的差值
        return mx - int(ss.replace(ss[0],'0'))

Explore

替换第一个非'9'的数字是一种策略，它便于实现且效果显著。替换最左侧的非'9'数字能立即增加数字的大小，因为数字的值由左至右逐位减小。虽然替换出现次数最多的非'9'数字在理论上可能提供更大的增幅，但这种策略计算复杂，并不总是必要的，尤其是在数字长度较短时。此外，最左侧的非'9'数字对整个数值的影响最大，因此优先替换它可以快速达到增大数值的目的。

确实，直接将最高位的'1'替换为'0'会导致数字前导零的问题，从而使数字的有效位数减少。为了避免这个问题，我们应该判断如果数字的最高位是'1'，并且该数字不是唯一一位，那么它的有效替换应该是将它替换为'1'之后的最小有效数字，而不是'0'。例如，如果数字为1000，我们应该将最高位的'1'替换为'0'，然后从数学的角度忽略前导零，视为0。实际操作时，可以通过字符串处理技术去除前导零，或者采用条件判断避免这种替换。

如果最高位已经是'0'，那么最高位的数字已经是可能的最小值了，此时应考虑替换第一个非'0'的数字为'0'，以便进一步减小数值。例如，对于数字0203，最高位已是'0'，所以我们可以考虑将'2'替换为'0'，得到0003，即3。这种情况下，处理前导零的方式依然是将其从数学计算的角度忽略。

为了确保替换结果不产生非法的数字格式，如前导零，我们在替换后应该将结果字符串转换为整数。整数类型自然会去除前导零。例如，将字符串'0003'转换为整数后，它就会变成3。在编程实现时，可以通过字符串到整数的转换来自动处理前导零的问题，确保所有操作和计算都在有效的整数上进行。