题目描述
思路解析
一句话答案：LeetCode 1689 十-二进制数的最少数目：每个十-二进制数每位只能放 0 或 1，凑出数字 d 就要 d 个，所以答案是 n 里最大的那位数字，逐位取最大，时间 O(n)。
十-二进制数是什么，题目到底要我们求几个
先把十-二进制数说清楚：它也是十进制数，只是每一位上只能写 0 或 1，还不带前导零，像 101、1100 都算，112、3001 就不算。题目给一个十进制字符串 n，要你挑几个这样的数，加起来正好等于 n，并且用的个数越少越好。题面例子里 n = 32 用 3 个，n = 82734 用 8 个。
真去把 n 拆成一堆十-二进制数，会卡在哪
拆数这条路一上来就发怵：面对 82734，你得试着拼几个每位非 0 即 1 的数把它凑齐，还得保证个数最少。可这样的数怎么搭配、搭几个，组合多得数不过来，手一个个试既慢又难保证最优。要想少走弯路，得先弄清一件事：到底是什么在决定最少要几个。
为什么答案就是 n 里最大的那位数字
把每一位单独拎出来看，事情就清楚了。十-二进制数在每一位只能贡献 0 或 1，要让若干个数在某一位加出数字 d，至少得有 d 个数在这位都放 1。那么 n 里数字最大的那一位，就直接顶住了你要准备多少个数——这一位是 d，就非得凑够 d 个数不可。
而其它位都比它小，在这 d 个数里顺带就能凑齐：哪一位要几个 1，就挑其中几个数在那位放 1、剩下放 0，各位互不打架。于是最少个数只由最难凑的那一位定死，答案就是 n 各位里最大的那个数字。82734 里最大是 8，答案就是 8。
三种语言怎么写，Python 为什么一行就够
既然只要找最大数字，逐位扫过去、拿每一位刷新一个记最大值的变量就行。Python 更省事，一句 int(max(n)) 搞定：n 全由数字字符组成，而字符 '0' 到 '9' 的排列顺序跟它们代表的数值大小完全一致，所以直接对字符串取 max 拿到的就是最大那个数字字符，外面套个 int 转成整数。C++ 和 Java 没有这种字符串直接取 max 的便利，就老老实实循环逐位，把字符减 '0' 还原成数字再取最大。
82734 一位位比下去，8 怎么留到最后
从左往右扫，手里记最大值的变量从 0 起。第一位 8，比 0 大，抬到 8；第二位 2、第三位 7 都没超过 8，按兵不动；第四位 3、第五位 4 同样比 8 小，稳稳停在 8。五位全看完，最大的就是开头那个 8，答案是 8。再拿 32 走一遍：3 先把它顶到 3，2 没超过，结果 3，跟题面给的两个输出都对得上。
简单题偏爱把人绕进复杂里
真动手去拆数，拼一堆十-二进制数再数个数，忙半天绕回原点，取最大数字本就够了；把各位数字加起来、或求个平均当答案，方向一开始就偏，个数只由最难凑的那位卡着，和总和、平均都不相干——82734 各位相加是 24，答案却还是 8；比较时把相等也当成要刷新，虽不影响最大值，却容易让判断变松，严格更大才刷新最干净。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这套:答案 = n 里最大的那一位数字。逐位扫,拿当前数字去刷新「见过的最大数字」,扫完它就是答案。下面每帧都在套它。
总览 · 最大数字清零,从最左开扫：上面这排是 "27340681" 拆开的 8 位数字。开扫前,记最大数字的 curMax 先清成 0。我们要做的就是从最左第 0 位往右走,每看到一位,就拿它跟 curMax 比一比,谁大留谁。扫到头,curMax 就是答案。
读第 0个 · "2"：先看第 0 位,是数字 2。手里的 curMax 还是 0,拿 2 跟它比一下。
刷新 · curMax 升到 2：2 比 0 大,curMax 更新成 2,把这位标成绿色,它是眼下的「最大数字冠军」。这位处理完变蓝,接着往右。
读第 1个 · "7"：第 1 位是 7,明显比手里的 2 大。拿它跟 curMax 比。
刷新 · curMax 升到 7：7 把 2 顶下去,curMax 升到 7,绿色冠军位从第 0 位挪到第 1 位。记住这个 7,后面就看谁还能超过它。
读第 2个 · "3"：第 2 位是 3,看着不算小,可手里的 curMax 已经是 7 了,先比一比再说。
不刷新 · curMax 还是 7：3 比 7 小,curMax 一动不动,还是 7,冠军位仍停在第 1 位的 7。这位看完直接变蓝。
读第 3个 · "4"：第 3 位是 4,比刚才的 3 大一点,但还得跟 curMax 的 7 较量。
不刷新 · curMax 还是 7：4 没干过 7,curMax 照旧是 7。这一路你会发现,只要没碰到更大的数字,curMax 就稳稳不动。
读第 4个 · "0"：第 4 位是 0,这是最小的数字。标成红色提醒你:0 是绝不可能成为最大数字的,但流程一视同仁,照样拿它比一下。
不刷新 · curMax 还是 7：0 当然比 7 小,curMax 纹丝不动。顺带说一句:这一位是 0,意味着所有加数在这一位都放 0 就行,它对答案没有任何压力。
读第 5个 · "6"：第 5 位是 6,离 7 只差一点点,是个很像样的挑战者。拿它跟 curMax 比。
不刷新 · 6 差一点没超过：6 比 7 小,就差这么一口气,curMax 还是 7。可见相等或更小都不刷新,必须严格更大才行。
读第 6个 · "8"：第 6 位是 8,这是全题最关键的一位。它比手里的 7 还大,盯紧了。
刷新 · curMax 升到 8(答案诞生)：8 把 7 顶下去,curMax 升到 8,绿色冠军位跳到第 6 位。这个 8 就是后面再也无人超越的最大数字,也就是最终答案。
读第 7个 · "1"：最后一位是 1,很小。例行公事拿它跟 curMax 比一下。
不刷新 · curMax 定格 8：1 远小于 8,curMax 稳稳停在 8。整串也就扫到头了。
扫描完毕 · 看 curMax：8 位数字全看过一遍,整排都变蓝了。现在 curMax 里攥着的,就是整串里最大的那位数字。
完成 · 答案 8：curMax 定格在 8,来自绿色标出的第 6 位那个 8。它就是把 n 拆成十-二进制数所需要的最少个数。前面虽有 7、有 6 紧追,但都没能超过它。
兑现 · 8 个十-二进制数拼回 n：为什么这个 8 真能凑成?准备 8 个十-二进制数,对 n 的每一位 d,就让其中 d 个数在这一位放 1、其余放 0,这一位的和正好是 d。每一位都这么配,8 个数加起来就是 n。位上最大的数字是 8,8 个数刚好够用,所以 8 就是最少个数,既不能再少,也用不着更多。
边界三例:"1" 答案 1;全是 1 的 "111" 还是 1;"9" 要满 9 个,9 是单位数字上限。
面试重点:瓶颈在最大数字、无需构造;Python 字符串取 max 成立;时间 O(n) 空间 O(1)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def minPartitions(self, n: str) -> int: return int(max(n))复杂度
- 时间：O(n)，n 为字符串长度。每一位只看一遍,做一次比较和取最大,整体是一遍线性扫描;扫到 9 时其实可以提前收手,但最坏仍是看完全串
- 空间：O(1)，自始至终只用一个整数记最大数字,峰值占用是常数,跟串多长无关;并没有真去构造那些十-二进制数
易错点
面试追问把动画讲成自己的话
追问这题为什么不用真的去构造那些十-二进制数?
追问Python 直接 max(n) 在字符串上比,会不会出问题?
追问这题的时间和空间复杂度是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
需要教语言的最少人数
LeetCode 1733 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题