LeetCode-Go 题解 12：Integer to Roman 整数转罗马数字的贪心算法实现

导读

本文基于开源仓库 LeetCode-Go 中 0012.Integer-to-Roman 题解文档 及其配套源码，完整拆解 LeetCode 第 12 题「整数转罗马数字」的规则、贪心思路与 Go 实现。读完本文，你将掌握罗马数字的七符号表示法与六条减法特例、从大到小逐位扣减的贪心算法原理，以及如何在本地运行该题的单测验证实现正确性，并顺带了解与之互为镜像的第 13 题（罗马数字转整数）的实现对照。

题目背景：罗马数字的表示规则

罗马数字由七个不同符号组成，每个符号对应一个固定的数值：

符号	数值
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

在通常情况下，罗马数字按照从大到小、从左到右的顺序书写。例如 2 写作 II（两个 1 相加），12 写作 XII（即 X + II），27 写作 XXVII（即 XX + V + II）。

然而数字 4 并不会写成 IIII，而是写作 IV：因为 I 位于 V 的左边，表示"大数 5 减去小数 1"，得到 4。同样的原理适用于数字 9，写作 IX。这种"左减右加"的减法规则一共只有六种情况：

• I 可以放在 V（5）和 X（10）的左边，表示 4 和 9；
• X 可以放在 L（50）和 C（100）的左边，表示 40 和 90；
• C 可以放在 D（500）和 M（1000）的左边，表示 400 和 900。

正是这六个"减法组合"（IV、IX、XL、XC、CD、CM）构成了本题实现的核心难点。

题目要求与约束

题目要求：给定一个整数 num，将其转换为对应的罗马数字字符串。原文档给出了五个标准示例：

• num = 3 → "III"
• num = 4 → "IV"
• num = 9 → "IX"
• num = 58 → "LVIII"（L = 50, V = 5, III = 3）
• num = 1994 → "MCMXCIV"（M = 1000, CM = 900, XC = 90, IV = 4）

约束条件非常明确：1 <= num <= 3999。这意味着输入范围有限，我们可以用一张覆盖全部合法区间的"数值—符号"对照表来一次性解决问题，无需考虑 4000 以上的扩展写法（如带横线的 5000 等）。

核心思路：从大到小的贪心算法

原文档的解题思路一句话点破本质：

依照题意，优先选择大的数字，解题思路采用贪心算法。将 1-3999 范围内的罗马数字从大到小放在数组中，从头选择到尾，即可把整数转成罗马数字。

这里的贪心策略是：每一步都尽可能使用当前能用的最大面值符号去"消化"剩余数值。由于罗马数字的符号体系是"面值越大越靠左"，且我们已将六种减法组合展开为独立"面值"，因此只要按数值从大到小依次尝试，就能保证每一步的选择都是局部最优，而局部最优叠加起来恰好构成全局唯一正确的罗马数字表示。

之所以需要把 CM（900）、CD（400）、XC（90）、XL（40）、IX（9）、IV（4）这六个减法组合作为独立条目放入表中，是因为它们本质上是"不可再拆分"的复合面值：例如 1994 必须写成 MCMXCIV，其中 CM、XC、IV 各自对应一次减法语义，而不是简单的 M + D + ... 相加。

源码实现详解

仓库中的核心实现位于 12. Integer to Roman.go，与题解文档中的代码完全一致：

func intToRoman(num int) string {
	values := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
	symbols := []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}
	res, i := "", 0
	for num != 0 {
		for values[i] > num {
			i++
		}
		num -= values[i]
		res += symbols[i]
	}
	return res
}

逐段拆解这段代码：

1. 两张对齐的查找表：values 数组将 1–3999 范围内所有"语义不可拆分"的面值从大到小排列（含六个减法组合），symbols 数组存放与每个面值一一对应的罗马符号。两个数组通过相同下标 i 绑定，构成一张贪心查表。

2. 外层循环 for num != 0：只要剩余数值没有归零，就继续选面值。因为所有面值最小为 1，所以循环必然终止。

3. 内层循环 for values[i] > num { i++ }：从当前下标开始向右扫描，跳过所有比剩余数值大的面值，停在第一个"不大于剩余数值"的最大面值处。注意 i 只增不减——由于 num 单调递减，已跳过的更大面值后续永远不会再用，因此这个写法是正确且高效的。

4. 扣减与拼接：num -= values[i] 完成一次贪心扣减，res += symbols[i] 将对应符号追加到结果字符串末尾。由于每次扣减后面值可能依然可用（例如 num = 3 时连续三次选中 I），外层循环会自然处理这种"重复使用同一面值"的情况。

以 num = 1994 走一遍流程：依次选中 M（1000，余 994）→ CM（900，余 94）→ XC（90，余 4）→ IV（4，余 0），拼接得到 "MCMXCIV"，与题目示例完全吻合。

时间复杂度与空间复杂度

• 时间复杂度：外层循环最多执行约 len(values) 级别次数的"选择 + 扣减"，每次内层扫描累计也只遍历一遍查找表，因此整体复杂度为 O(1)（常数级别，因为 values 表长度固定为 13，且输入范围被限制在 3999 以内）。
• 空间复杂度：只使用了两个定长切片与一个字符串累加结果，为 O(1)。

测试用例验证

仓库为本题配备了完整的表驱动单测 12. Integer to Roman_test.go，覆盖了题目给出的全部五个官方示例，并额外补充了边界与常规用例：

输入	期望输出
3	"III"
4	"IV"
9	"IX"
58	"LVIII"
1994	"MCMXCIV"
123	"CXXIII"
120	"CXX"

其中 123 与 120 是题解作者额外添加的用例，分别覆盖了"百位 + 十位 + 个位"的一般情形（C + XX + III）与"末位为零"的情形（C + XX），能有效验证减法组合之外的常规累加路径。测试函数 Test_Problem12 遍历全部用例并打印输入输出对照，运行时输出形如 【input】:1994 【output】:MCMXCIV。

如何在本地运行

本仓库以 module github.com/halfrost/LeetCode-Go（见 go.mod，Go 1.19）组织代码，所有题解位于 leetcode/ 目录。在仓库根目录执行：

go test -v -run Test_Problem12 ./leetcode/0012.Integer-to-Roman/

即可单独运行本题测试。若想按仓库约定产出全量覆盖率报告，可执行仓库自带的 gotest.sh 脚本（其内部使用 go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...），该脚本一次性地为 leetcode/ 下所有题解生成合法且可被 Codecov 解析的单一覆盖率文件。

配套对照：第 13 题 Roman to Integer

整数转罗马数字（本题）与罗马数字转整数（第 13 题）互为逆运算，仓库中同样收录了后者：0013.Roman-to-Integer。其实现 13. Roman to Integer.go 采用从右往左扫描的策略：维护一个"上一个字符的数值"lastint，当当前字符数值小于 lastint 时做减法、否则做加法，从而自然处理 IV、IX 这类左减场景：

var roman = map[string]int{
	"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000,
}

func romanToInt(s string) int {
	if s == "" {
		return 0
	}
	num, lastint, total := 0, 0, 0
	for i := 0; i < len(s); i++ {
		char := s[len(s)-(i+1) : len(s)-i]
		num = roman[char]
		if num < lastint {
			total = total - num
		} else {
			total = total + num
		}
		lastint = num
	}
	return total
}

两题放在一起对比学习效果最佳：第 12 题是"查表 + 贪心扣减"的构造视角，第 13 题是"逆向扫描 + 左减右加"的解析视角，二者共享同一套七符号表与六条减法规则，是理解罗马数字体系的一对绝佳练习题。

小结

LeetCode-Go 仓库对第 12 题的题解文档与源码保持高度一致：核心解法是将 13 个"不可拆分面值"（7 个基本符号 + 6 个减法组合）按从大到小排列，用贪心策略逐次扣减并拼接符号。该实现代码极简、无需哈希表、无分支判断，且由于输入被限制在 1–3999，时间和空间复杂度均为 O(1)。配合仓库提供的表驱动测试用例，读者可以快速验证算法在边界值、减法组合与常规数值上的正确性。