M1689.十-二进制数的最少数目

greedy, https://leetcode.cn/problems/partitioning-into-minimum-number-of-deci-binary-numbers/

如果一个十进制数字不含任何前导零，且每一位上的数字不是 0 就是 1 ，那么该数字就是一个 十-二进制数 。例如，101 和 1100 都是 十-二进制数，而 112 和 3001 不是。

给你一个表示十进制整数的字符串 n ，返回和为 n 的 十-二进制数 的最少数目。

示例 1：

输入：n = "32"
输出：3
解释：10 + 11 + 11 = 32

示例 2：

输入：n = "82734"
输出：8

示例 3：

输入：n = "27346209830709182346"
输出：9

提示：

• 1 <= n.length <= 10^5
• n 仅由数字组成
• n 不含任何前导零并总是表示正整数

这道题要求我们用只包含 0 和 1 的十-二进制数来累加得到给定的十进制大整数 n，并且要求所用的数字数目最少。

方法解析

如果要在某一位上累加得到数字 d（d 是 0 到 9 之间的整数），由于我们每次只能加上一个只包含 0 和 1 的十-二进制数，所以我们至少需要 d 个这样的数十-二进制数才能让这一位的和等于 d。

比如，想要凑出 "32"：

• 十位上的数字是 3，意味着至少需要 3 个数的十位包含 1；
• 个位上的数字是 2，意味着至少需要 2 个数的个位包含 1。
• 因为所有位上的数是同步加的，为了满足所有位上的要求，我们需要的最少十-二进制数的数量就是给定字符串中的 最大字符（即最大的那个数字）。在前面的例子中，需要的最少数目即为 max(3, 2) = 3。

因此，我们要做的仅仅是从字符串 n 中找出最大的字符，然后将其转化为整数返回即可。

Python 3 代码

class Solution:
    def minPartitions(self, n: str) -> int:
        # 直接找出字符串中的最大字符，并转换为整数
        return int(max(n))

复杂度分析

• 时间复杂度: $O(L)$，其中 $L$ 是字符串 n 的长度。我们需要遍历整个字符串一次来找出最大的字符，时间复杂度与字符串长度成正比。对于上限 ${10}^5$ 的长度，这个操作是极快的。
• 空间复杂度: $O(1)$。我们仅使用了额外的常数级空间来保存计算得到的最大字符。