13. 罗马数字转整数

https://leetcode.cn/problems/roman-to-integer/description/?envType=study-plan-v2&envId=top-interview-150

我们显然可以总结出一这么一个规律:罗马数字如果大的数放在小的数右边就是代表这个数是减操作（最又侧的大数减左侧的小的数之和）
比如:IV=5-1=4,IX=10-1=9,XL=50-10=40, XC=100-10=90, CD=500-100=400, CM=1000-100=900，那我们这要将这些升序数找出来就行，这就可以用到我们的单调栈来解决。

class Solution {

    public static void main(String[] args) {
        String s = "IIIV";
        System.out.println(new Solution().romanToInt(s));
    }

    static HashMap<Character, Integer> map = new HashMap<Character, Integer>();

    static { //用静态代码块初始化
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
    }

    public int romanToInt(String s) {
        int res = 0, sum = 0;
        //单调增栈
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            int num = map.get(s.charAt(i));
            if(stack.empty() || num > stack.peek()) {//当前数字大于前一个数字，则直接入栈
                stack.push(num);
            } else { //当前数字小于等于前一个数字，则将栈中数算出，并清空栈将当前数进栈
                sum = stack.pop();
                while(!stack.empty()) {
                    sum -= stack.pop();
                }
                res += sum;
                stack.push(num);
            }
        }
        //最后栈里面可能还有数把这些数算一下
        if(!stack.empty()) {
            sum = stack.pop();
            while(!stack.empty()) {
                sum -= stack.pop();
            }
            res += sum;
        }
        return res;
    }
}