LeetCode Roman to Integer 羅馬數字轉整數 (單遍掃描)

問題

將合法羅馬數字 (1~3999) 轉為整數。規則：同值累加，小值在大值左邊相減 (如 IV=4)，右邊相加 (如 VI=6)。

掃描算法

從右向左遍歷，維護當前最大值。若當前字符值 ≥ 最大值，累加並更新最大值；否則減去。因為右側必為同位或更高位。

代碼 (C++)

class Solution {
public:
    int romanToInt(string s) {
        unordered_map mp = {
            {'I',1},{'V',5},{'X',10},{'L',50},
            {'C',100},{'D',500},{'M',1000}
        };
        int res = 0, maxVal = 0;
        for (int i = s.size()-1; i >= 0; --i) {
            int val = mp[s[i]];
            if (val >= maxVal) { res += val; maxVal = val; }
            else res -= val;
        }
        return res;
    }
};

正確性說明

羅馬數字從高位到低位書寫，唯一例外是減法標記 (如 IV) 出現在高位左側。右向左掃描時，減法標記必在對應高位右側，故遇到小於右側最大值時即為減法。

複雜度

O(n) 時間，n=字符串長度 (≤15)。O(1) 空間。