What is the key pattern in Maximum Difference by Remapping a Digit?

The main pattern is a greedy choice plus invariant validation: select the first digit to remap to maximize or minimize the number while preserving length.

Can multiple digits be remapped in this problem?

No, the problem restricts you to remapping exactly one digit. Attempting multiple remaps changes the rules and results.

How do leading zeros affect the solution?

Leading zeros are invalid, so when minimizing, avoid remapping the first digit to zero. Choose a later non-zero digit if necessary.

What is the time complexity of the greedy solution?

Time complexity is O(log num) because each digit is processed once to determine the maximum and minimum remapping.

Why does remapping the first non-nine digit maximize the number?

Changing the first non-nine digit to 9 produces the largest increase possible without altering the number of digits, following the greedy approach.

#2566

Easy

auto_awesome贪心·invariant

LeetCode 题解工作台

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

给你一个整数 num 。你知道 Danny Mittal 会偷偷将 0 到 9 中的一个数字替换成另一个数字。请你返回将 num 中恰好一个数字进行替换后，得到的最大值和最小值的差为多少。注意：当 Danny 将一个数字 d1 替换成另一个数字 d2 时，Danny 需要将 num 中…

数学贪心

题目描述

给你一个整数 num 。你知道 Danny Mittal 会偷偷将 0 到 9 中的一个数字替换成另一个数字。

请你返回将 num 中 恰好一个 数字进行替换后，得到的最大值和最小值的差为多少。

注意：

当 Danny 将一个数字 d1 替换成另一个数字 d2 时，Danny 需要将 num 中所有 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⁸

lightbulb

解题思路

方法一：贪心

我们先将数字转为字符串 $s$ 。

要得到最小值，我们只需要将找到字符串 $s$ 的第一个数字 $s[0]$ ，然后把字符串中所有的 $s[0]$ 替换成 $0$ 即可。

要得到最大值，我们需要找到字符串 $s$ 中第一个不是 $9$ 的数字 $s[i]$ ，然后把字符串中所有的 $s[i]$ 替换成 $9$ 即可。

最后返回最大值和最小值的差即可。

时间复杂度 $O(\log n)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为数字 $\textit{num}$ 的值。

1

2

3

4

5

6

7

8

9

class Solution:
    def minMaxDifference(self, num: int) -> int:
        s = str(num)
        mi = int(s.replace(s[0], '0'))
        for c in s:
            if c != '9':
                return int(s.replace(c, '9')) - mi
        return num - mi

speed

复杂度分析

指标	值
时间	O(\log \textit{num})
空间	O(\log \textit{num})

psychology

面试官常问的追问

外企场景

question_mark
Check for off-by-one errors when remapping the first digit.
question_mark
Consider numbers with repeated digits and how remapping affects multiple positions.
question_mark
Verify handling of leading zeros in the minimized number to avoid invalid results.

warning

常见陷阱

外企场景

error
Attempting to remap digits that do not maximize or minimize the number.
error
Ignoring the effect of leading digits and accidentally producing an invalid number.
error
Failing to consider multiple occurrences of the same digit for a consistent remapping.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow remapping multiple digits instead of only one for maximum impact.
arrow_right_alt
Calculate the difference if remapping must not produce a leading zero.
arrow_right_alt
Extend to negative numbers with similar remapping rules.

help

常见问题

外企场景

继续练习

#2578 最小和分割 #2541 使数组中所有元素相等的最小操作数 II #2591 将钱分给最多的儿童