題目：

在這題中是考如何有效地將羅馬數字轉換為整數。羅馬數字是一種基於七個符號的數字系統：I、V、X、L、C、D 和 M。這些符號的數值分別為：

• I = 1
• V = 5
• X = 10
• L = 50
• C = 100
• D = 500
• M = 1000

解題思路

觀察出一個規律，當前字母代表數字小於下一個字母代表數字，則減去當前字母代表數字，反之則累加，

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> map = {
            {'I', 1},
            {'V', 5},
            {'X', 10},
            {'L', 50},
            {'C', 100},
            {'D', 500},
            {'M', 1000}
        };

        int sum = 0;
        for (int i = 0; i < s.size(); i++) {
            if (i == s.size()-1) { // 最後一個則直接累加
                sum += map[s[i]];
            } else if (map[s[i]] >= map[s[i+1]]) {
                sum += map[s[i]];
            } else { // map[s[i]] < map[s[i+1]]
                sum -= map[s[i]];
            }
        }
        return sum;
    }
};

時間複雜度：O(n)
空間複雜度：O(1)

參考：
#13. Roman to Integer