如何把整数转换成罗马数字？（LeetCode 12）

简化版

整数转罗马数字的核心是按数值从大到小贪心匹配。罗马数字有几个特殊减法形式：IV=4、IX=9、XL=40、XC=90、CD=400、CM=900。把这些特殊值和普通值一起放进表里，从 1000 到 1 依次扣减，能扣就追加对应符号，直到数字变成 0。

例如 1994：先取 1000 得 M，再取 900 得 CM，再取 90 得 XC，再取 4 得 IV，结果 MCMXCIV。

详细版

String intToRoman(int num) {
    int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    StringBuilder sb = new StringBuilder();

    for (int i = 0; i < values.length; i++) {
        while (num >= values[i]) {
            num -= values[i];
            sb.append(symbols[i]);
        }
    }
    return sb.toString();
}

这是一种典型贪心：每次选择当前不超过剩余数字的最大罗马单位。因为罗马数字标准写法本来就是从大到小排列，且 4、9、40、90、400、900 这些特殊减法项已经放进候选表，所以局部最优选择会拼出合法且规范的结果。

完整版教学

一、先理解罗马数字规则

罗马数字由 I,V,X,L,C,D,M 组成，分别表示 1,5,10,50,100,500,1000。普通情况下，数字从大到小排列，相同符号可重复，表示相加。例如 III=3，VIII=8，XXVII=27。

但罗马数字有减法表示：小符号放在大符号左边表示相减。面试题通常只允许以下六种：

数值	罗马表示	含义
4	IV	5 - 1
9	IX	10 - 1
40	XL	50 - 10
90	XC	100 - 10
400	CD	500 - 100
900	CM	1000 - 100

这些特殊项必须纳入转换表，否则 4 会错误写成 IIII，9 会错误写成 VIIII。

二、为什么可以贪心

目标是把 num 分解成若干罗马单位的和，并按从大到小输出。罗马数字规范写法要求大的单位尽量靠前，因此每一步都应该选不超过剩余值的最大单位。

num = 1994
最大可用值 1000 -> M, 剩余 994
最大可用值 900  -> CM, 剩余 94
最大可用值 90   -> XC, 剩余 4
最大可用值 4    -> IV, 剩余 0
结果: MCMXCIV

如果没有把 900 放进表，贪心会先选 500，然后拼出不规范形式。也就是说，贪心成立的前提不是只有七个基础符号，而是把特殊减法组合也视为独立面额。

三、转换表如何设计

候选表要按数值降序排列：

int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

每个 values[i] 和 symbols[i] 一一对应。循环到某个面额时，只要 num >= values[i]，就扣掉这个值并追加符号。扣到不能扣为止，再进入下一个更小面额。

四、代码流程和不变式

可以维护一个不变式：已经输出的罗马符号所代表的值 + 当前 num = 原始输入值。每次追加符号时，同时从 num 扣掉对应数值，不变式保持成立。

初始: output="", num=58
50: output="L", num=8
5 : output="LV", num=3
1 : output="LVI", num=2
1 : output="LVII", num=1
1 : output="LVIII", num=0

当 num 变为 0，输出部分刚好等于原始数字。因为候选表降序，输出顺序天然合法。

五、复杂度为什么近似常数

LeetCode 12 的输入范围通常是 1 <= num <= 3999。候选表长度固定 13，循环次数也被罗马数字长度上界限制，所以可以说时间复杂度是 O(1)，空间复杂度是 O(1)。如果把输入范围抽象成任意大整数，则时间与输出长度相关。

讨论角度	结论
面试题固定范围	O(1) 时间，O(1) 额外空间
泛化到任意范围	O(k) 时间，k 为输出长度
实现细节	用 `StringBuilder` 避免频繁字符串拼接

六、另一种写法：按千百十个拆位

也可以预先列出每一位的所有可能：

String[] thousands = {"", "M", "MM", "MMM"};
String[] hundreds = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
String[] tens = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
String[] ones = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
return thousands[num / 1000]
     + hundreds[num % 1000 / 100]
     + tens[num % 100 / 10]
     + ones[num % 10];

这种写法更短，但需要记住四张表。贪心表法更容易解释，也更能展示对特殊减法规则的理解。

七、面试现场如何验证

建议至少验证这些样例：

3 -> III：重复基础符号。
4 -> IV：个位减法。
9 -> IX：个位另一个减法。
58 -> LVIII：普通加法组合。
1994 -> MCMXCIV：千、百、十、个位都涉及。

验证时要专门覆盖 4 和 9 系列，因为这正是本题最容易写成非规范罗马数字的地方。

八、常见误区与追问

误区：只列 1000,500,100,50,10,5,1 七个值。 会把 4、9、40、90、400、900 转成非规范形式。
误区：把候选表升序排列。 贪心需要先选最大可用单位，升序会输出错误顺序。
误区：每个面额只扣一次。 3000 需要追加三次 M，必须用 while。
误区：频繁使用字符串 + 拼接。 在循环中可能产生较多临时对象，建议用 StringBuilder。
追问：为什么 1994 不是 MDCCCCLXXXXIV？ 标准写法使用 CM 和 XC 表示 900 和 90。
追问：为什么贪心是正确的？ 因为候选面额包含所有特殊减法组合，标准罗马数字按降序选择最大合法单位。

九、加强记忆

罗马数字转换不是单纯七个符号相加，要额外记住六个减法项。
把普通值和减法值合成一张降序表，问题就变成贪心扣减。
每次选不超过剩余值的最大面额，追加符号并扣掉数值。
while 负责同一符号重复，例如 III、MMM。
高频边界看 4,9,40,90,400,900,1994。

简化版

详细版