整数转罗马数字

下面这排格子就是 13 个面值。看一个指针从左往右扫,能减就减、减完接着减,减不动才往右挪。盯住「剩余」和「已拼」两个数怎么变。

起步 · 剩余 1994：指针指向最大面值 1000(符号 M)。问:1000 能从 1994 里减掉吗?

1000 ≤ 1994 · 减!：能!1000 ≤ 1994,减掉,剩余变 994,结果拼上 M。还停在 1000,看能否再减。

1000 > 994 · 减不动：这次 1000 > 994,减不动。1000 这格封存变灰,指针挪到 900。

900 ≤ 994 · 减!：900 的符号是减法形式 CM。900 ≤ 994,减掉,剩余变 94,结果变 MCM。

900 > 94 · 减不动：900 减不动 94,封存,指针挪到 500。

500 > 94 · 跳过：500 比 94 大,减不动,指针滑到 400。

400 > 94 · 跳过：400 也比 94 大,继续滑到 100。

100 > 94 · 跳过：100 只比 94 大一点点,还是减不动,滑到 90。

90 ≤ 94 · 减!：90 的符号是 XC。90 ≤ 94,减掉,剩余只剩 4,结果变 MCMXC。

90 > 4 · 减不动：90 减不动 4,封存,指针挪到 50。

50 > 4 · 跳过：50 比 4 大,滑到 40。

40 > 4 · 跳过：40 也比 4 大,滑到 10。

10 > 4 · 跳过：10 比 4 大,滑到 9。

9 > 4 · 跳过：9 还是比 4 大,滑到 5。

5 > 4 · 跳过：5 比 4 大一点,滑到 4(符号 IV)——终于来到能减的面值。

4 ≤ 4 · 减!最后一步：4 的符号是减法形式 IV。4 ≤ 4,减掉,剩余归 0!结果拼成 MCMXCIV。

剩余 = 0 · 完成：剩余到 0,结束。绿色的 4 个面值(M、CM、XC、IV)就是用到的,按顺序拼起来正是答案 MCMXCIV。

再演一例 · num = 3000：换个数 3000 再走一遍,这次专看雷区里说的同一面值连减。指针还是停在最大面值 1000(M)。

3000 ≥ 1000 · 第 1 次减：1000 ≤ 3000,减掉,剩余变 2000,结果拼上 M。注意指针没右移——还在 1000 上,看还能不能再减。

2000 ≥ 1000 · 第 2 次减：还能减!1000 ≤ 2000,再减一次,剩余 1000,结果变 MM。同一格 1000 被 while 反复用——这就是「连减」。

1000 ≥ 1000 · 第 3 次减：第 3 次:1000 ≤ 1000,减掉,剩余归 0!结果 MMM。后面的面值全用不上(变灰)。一个 while 在同一面值上连减三次,3000 就这么拼出来——这正是雷区②要的写法。

关键魔法在面值表:把 CM(900)、CD(400)、XC(90)、XL(40)、IX(9)、IV(4) 这 6 个减法形式也当成「面值」塞进表里,贪心就再不用判断何时该用减法写法。

雷区实演 · 面值表漏了 IV：假如面值表漏掉了 4(IV),轮到剩余 4 时只剩面值 1 可用,连减四次写出 IIII——这正是减法形式必须进表的原因。

边界三连：先想最小减法形式(4)、最大重复(3000)、普通累加(58)三种,代码就稳了。

面试追问：把「贪心为何对」和「O(1)」讲清楚,是这题面试的得分点。