Medium

题目描述

给你一个整数 num。你可以对 num 执行两次以下操作：

  • 选择一个数字 x（0 <= x <= 9）
  • 选择另一个数字 y（0 <= y <= 9）。注意 y 可以等于 x
  • 将 num 十进制表示中所有出现的 x 替换为 y

分别对 num 独立执行这两次操作，得到结果 a 和 b。

返回 a 和 b 之间的最大差值。

注意：a 和 b 都不能有前导零，且不能为 0。

示例 1：

输入：num = 555
输出：888
解释：第一次选择 x = 5, y = 9，得到 a = 999
第二次选择 x = 5, y = 1，得到 b = 111
最大差值 = 999 - 111 = 888

示例 2：

输入：num = 9
输出：8
解释：第一次选择 x = 9, y = 9，得到 a = 9
第二次选择 x = 9, y = 1，得到 b = 1
最大差值 = 9 - 1 = 8

约束条件：

  • 1 <= num <= 10^8

解题思路

要获得最大差值，我们需要分别找到能使数字最大和最小的变换策略。

获得最大值的策略： 从左到右扫描数字字符串，找到第一个不是 9 的数字，将其替换为 9。这样可以最大化高位的值。如果所有数字都是 9，则保持不变。

获得最小值的策略：

  1. 如果首位数字不是 1，将首位及所有相同的数字替换为 1，这样可以最小化高位的值
  2. 如果首位数字是 1，则从第二位开始找到第一个不是 0 且不是 1 的数字，将其替换为 0

这样设计是因为：

  • 对于最大值：我们希望尽可能让高位变大
  • 对于最小值：我们希望尽可能让高位变小，但要避免产生前导零或结果为 0

通过贪心策略，我们可以在一次遍历中确定最优的变换方案。

推荐解法： 贪心算法，时间复杂度最优，代码简洁。

代码实现

class Solution {
public:
    int maxDiff(int num) {
        string s = to_string(num);
        
        // 获得最大值：找第一个不是9的数字，替换为9
        string maxStr = s;
        for (char& c : maxStr) {
            if (c != '9') {
                char target = c;
                for (char& ch : maxStr) {
                    if (ch == target) ch = '9';
                }
                break;
            }
        }
        
        // 获得最小值
        string minStr = s;
        if (minStr[0] != '1') {
            // 如果首位不是1，将首位替换为1
            char target = minStr[0];
            for (char& c : minStr) {
                if (c == target) c = '1';
            }
        } else {
            // 如果首位是1，找第一个不是0且不是1的数字，替换为0
            for (int i = 1; i < minStr.length(); i++) {
                if (minStr[i] != '0' && minStr[i] != '1') {
                    char target = minStr[i];
                    for (char& c : minStr) {
                        if (c == target) c = '0';
                    }
                    break;
                }
            }
        }
        
        return stoi(maxStr) - stoi(minStr);
    }
};

class Solution:
    def maxDiff(self, num: int) -> int:
        s = str(num)
        
        # 获得最大值：找第一个不是9的数字，替换为9
        max_str = s
        for c in s:
            if c != '9':
                max_str = s.replace(c, '9')
                break
        
        # 获得最小值
        min_str = s
        if s[0] != '1':
            # 如果首位不是1，将首位替换为1
            min_str = s.replace(s[0], '1')
        else:
            # 如果首位是1，找第一个不是0且不是1的数字，替换为0
            for i in range(1, len(s)):
                if s[i] != '0' and s[i] != '1':
                    min_str = s.replace(s[i], '0')
                    break
        
        return int(max_str) - int(min_str)

public class Solution {
    public int MaxDiff(int num) {
        string s = num.ToString();
        
        // 获得最大值：找第一个不是9的数字，替换为9
        string maxStr = s;
        foreach (char c in s) {
            if (c != '9') {
                maxStr = s.Replace(c, '9');
                break;
            }
        }
        
        // 获得最小值
        string minStr = s;
        if (s[0] != '1') {
            // 如果首位不是1，将首位替换为1
            minStr = s.Replace(s[0], '1');
        } else {
            // 如果首位是1，找第一个不是0且不是1的数字，替换为0
            for (int i = 1; i < s.Length; i++) {
                if (s[i] != '0' && s[i] != '1') {
                    minStr = s.Replace(s[i], '0');
                    break;
                }
            }
        }
        
        return int.Parse(maxStr) - int.Parse(minStr);
    }
}

var maxDiff = function(num) {
    const s = num.toString();
    
    // 获得最大值：找第一个不是9的数字，替换为9
    let maxStr = s;
    for (const c of s) {
        if (c !== '9') {
            maxStr = s.replaceAll(c, '9');
            break;
        }
    }
    
    // 获得最小值
    let minStr = s;
    if (s[0] !== '1') {
        // 如果首位不是1，将首位替换为1
        minStr = s.replaceAll(s[0], '1');
    } else {
        // 如果首位是1，找第一个不是0且不是1的数字，替换为0
        for (let i = 1; i < s.length; i++) {
            if (s[i] !== '0' && s[i] !== '1') {
                minStr = s.replaceAll(s[i], '0');
                break;
            }
        }
    }
    
    return parseInt(maxStr) - parseInt(minStr);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)n 为数字的位数，需要遍历字符串进行替换操作
空间复杂度O(n)需要存储字符串形式的数字