题目描述

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

算法分析

贪心

• 变成最大值的方法：将第一个非9的数全部变成9，即先找到第一个非9的数的位置k，再从该位置往后扫描，把该数全部变成9
• 变成最小值的方法：
  • 1、若第一个位是1，则往后找第一个非0的数全部变成0，即先找到第一个非0的数的位置k，再从该位置往后扫描，把该数全部变成9
  • 2、若第一个位不是1，则把第一个位数后面的相同的数值全部变成1，包括自己

细节特别多！

时间复杂度 $O(1)$

Java 代码

class Solution {
    public static int maxDiff(int num) {
        String nums = "" + num;
        int n = nums.length();
        String a = "";
        String b = "";
        //将第一个非9的数全部变成9
        int k = 0;
        while(k < n && nums.charAt(k) == '9')
        {
            a += nums.charAt(k);
            k ++;
        }
        if(k != n)
        {
            char t1 = nums.charAt(k);//当前数
            for(int i = k;i < n;i ++)
            {
                if(nums.charAt(i) == t1) a += '9';
                else a += nums.charAt(i);
            }
        }


        //若第一个位是1，则往后找第一个非0的数全部变成0
        //若第一个位不是1，则把该数全部变成1
        if(nums.charAt(0) == '1')
        {
            b += nums.charAt(0);
            k = 1;
            while(k < n && (nums.charAt(k) == '0' || nums.charAt(k) == '1')) 
            {
                b += nums.charAt(k);
                k ++;
            }
            if(k != n) 
            {
                char t2 = nums.charAt(k);
                for(int i = k;i < n;i ++)
                {
                    if(nums.charAt(i) == t2) b += '0';
                    else b += nums.charAt(i);
                }
            }

        }
        else 
        {
            char t2 = nums.charAt(0);
            for(int i = 0;i < n;i ++)
            {
                if(nums.charAt(i) == t2) b += '1';
                else b += nums.charAt(i);
            }
        }
        return Integer.parseInt(a) - Integer.parseInt(b);
   }
}