实战：整数转罗马数字

上一章我们将罗马数字转为整数，这一章反过来——将整数转为罗马数字。

首先要问一个问题：有什么策略可以将一个整数拆解成罗马数字的组合？

题目描述

LeetCode 12. 整数转罗马数字
给你一个整数，将其转为罗马数字。
罗马数字由七个基本符号表示：I(1), V(5), X(10), L(50), C(100), D(500), M(1000)。
此外有六个特殊组合：IV(4), IX(9), XL(40), XC(90), CD(400), CM(900)。
约束：1 <= num <= 3999

示例：

输入：num = 3749
输出："MMMDCCXLIX"
解释：
3000 = MMM
 700 = DCC
  40 = XL
   9 = IX

输入：num = 58
输出："LVIII"
解释：L = 50, V = 5, III = 3

贪心策略

现在我要问第二个问题：假设我们手里有所有面值的"硬币"（罗马数字符号），如何用最少的硬币凑出目标金额？

答案是贪心：每次尽可能选择最大面值的硬币。

比如凑 58：先用 L(50)，剩 8；再用 V(5)，剩 3；最后用 3 个 I(1)。结果是 LVIII。

但这里有个细节：我们不仅有 7 个基本符号，还有 6 个特殊组合（4, 9, 40, 90, 400, 900）。它们也是可用的"面值"。

所以策略是：把 13 个面值按降序排列，每次选最大的可用值。

解法：贪心算法

javascript

function intToRoman(num) {
    // 13 种面值，按降序排列
    const values = [
        1000, 900, 500, 400, 
        100, 90, 50, 40, 
        10, 9, 5, 4, 1
    ];
    const symbols = [
        'M', 'CM', 'D', 'CD', 
        'C', 'XC', 'L', 'XL', 
        'X', 'IX', 'V', 'IV', 'I'
    ];
    
    let result = '';
    
    for (let i = 0; i < values.length; i++) {
        // 当前面值能用多少次
        while (num >= values[i]) {
            result += symbols[i];
            num -= values[i];
        }
    }
    
    return result;
}

代码非常简洁：外层遍历每种面值，内层循环尽可能多地使用当前面值。

执行过程追踪

以 num = 3749 为例：

初始：num = 3749, result = ""

values[0] = 1000:
  3749 >= 1000, result = "M",    num = 2749
  2749 >= 1000, result = "MM",   num = 1749
  1749 >= 1000, result = "MMM",  num = 749
  749 < 1000,  退出内层循环

values[1] = 900:
  749 < 900,   跳过

values[2] = 500:
  749 >= 500,  result = "MMMD",  num = 249
  249 < 500,   退出

values[3] = 400:
  249 < 400,   跳过

values[4] = 100:
  249 >= 100,  result = "MMMDC", num = 149
  149 >= 100,  result = "MMMDCC", num = 49
  49 < 100,    退出

values[5] = 90:
  49 < 90,     跳过

values[6] = 50:
  49 < 50,     跳过

values[7] = 40:
  49 >= 40,    result = "MMMDCCXL", num = 9
  9 < 40,      退出

values[8] = 10:
  9 < 10,      跳过

values[9] = 9:
  9 >= 9,      result = "MMMDCCXLIX", num = 0
  0 < 9,       退出

返回 "MMMDCCXLIX"

复杂度分析

时间复杂度：O(1)。因为 num 最大是 3999，而最小面值是 1，所以总操作次数有上限（大约十几次）
空间复杂度：O(1)。映射数组大小固定

为什么贪心有效？

可能你会问：贪心算法不是经常失效吗？比如凑硬币问题，贪心就可能得到错误答案。

关键在于罗马数字的设计：

每位独立：个位、十位、百位、千位的表示互不干扰
特殊组合是唯一表示：4 只能用 IV 表示，不存在其他组合方式
无歧义性：不会出现"用小面值组合比用大面值更优"的情况

举个反例说明为什么普通硬币问题贪心失效：假设硬币面值是 [1, 3, 4]，凑 6。贪心选 4+1+1=6（3 枚），但最优是 3+3=6（2 枚）。

罗马数字不存在这种情况。面值的设计保证了贪心必定最优。

常见错误

遗漏特殊组合：只用 7 个基本符号会导致 4、9 等无法正确表示
顺序错误：必须严格降序排列，否则贪心逻辑失效
while 写成 if：一个面值可能使用多次，比如 3000 需要 3 个 M

本章小结

整数转罗马数字的核心是贪心：把所有面值（包括 6 个特殊组合）按降序排列，每次选择最大可用值。

贪心有效的前提是问题结构允许——罗马数字的设计保证了每位独立、无歧义，天然适合贪心。

这两道题（罗马数字互转）是很好的配对练习：

转整数：识别减法规则，从右向左遍历
转罗马：贪心选择，从大到小匹配

实战：整数转罗马数字 ​

题目描述 ​

贪心策略 ​

解法：贪心算法 ​

执行过程追踪 ​

复杂度分析 ​

为什么贪心有效？ ​

常见错误 ​

本章小结 ​

相关题目 ​