题目描述

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

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

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

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

样例

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

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

输入：num = 123456
输出：820000

输入：num = 10000
输出：80000

输入：num = 9288
输出：8700

限制

• 1 <= num <= 10^8

算法

(贪心) $O(\log n)$

1. 对于最大值，我们可以从最高位开始，向后找到第一个小于 9 的位置，将这个位置以及其它和这个位置相等的位置换成 9。
2. 对于最小值，如果最高位大于 1，则直接将最高位以及和最高位相同的位置换成 1。否则，从次高位开始，向后找到第一个大于 1 的位置，将这个位置以及其它和这个位置相等的位置换成 0。

时间复杂度

• 遍历常数 num 的数位，故时间复杂度为 $O(\log n)$。

空间复杂度

• 需要额外 $O(\log n)$ 的空间存储 num 的数位。

C++ 代码

class Solution {
public:
    int change(int x, int y, string s) {
        for (char &c : s)
            if (c == x + '0')
                c = y + '0';

        return stoi(s);
    }

    int maxDiff(int num) {
        string s = to_string(num);
        int a = num;

        for (int i = 0; i < s.size(); i++)
            if (s[i] < '9') {
                a = change(s[i] - '0', 9, s);
                break;
            }

        int b = num;
        if (s[0] > '1')
            b = change(s[0] - '0', 1, s);
        else {
            for (int i = 1; i < s.size(); i++)
                if (s[i] > '1') {
                    b = change(s[i] - '0', 0, s);
                    break;
                }
        }

        return a - b;
    }
};