十-二进制数的最少数目

记牢这套:答案 = 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)。