⚾️ 棒球比赛

📝 题目描述

​ 你现在是一名采用特殊赛制的棒球比赛的记录员。每场比赛由若干回合组成，每个回合都有一个得分记录。因此，比赛的得分信息可以由一个字符串序列records表示，序列中的每个字符串表示一个回合的得分记录。

​ 得分记录可以是数字（字符串表示）或一些特殊字符串，具体可选值如下。

1. 整数x：表示本回合新获得的分数x。
2. 字符串"D"：表示本回合获得的分数为前一次得分的两倍，本题保证该记录前总是存在一个有效的分数。
3. 字符串"+"：表示本回合获得的分数为前两次得分的总和，本题保证该记录前总是存在两个有效的分数。
4. 字符串"C"：表示前一次得分无效，本题保证该记录前总是存在一个有效的分数。

​ 现给定一场比赛的得分记录列表records，请你正确返回所有这场比赛所有回合的总得分。

🚀 示例

🖊️ 题解

​ 该题可以通过「栈」这一数据结构来模拟解决，具体步骤如下。

1. 创建一个辅助栈。
2. 遍历给定的字符串序列records。在遍历过程中，若当前记录record表示的是一个整数，则直接将其压入栈中；若当前记录record为字符串"D"，则取栈顶元素的值乘以2，并将计算结果压入栈中；若当前记录record为字符串"+"，则取栈顶的前两个元素的值相加，并将计算结果压入栈中；若当前记录record为字符串"C"，则直接弹出栈顶元素。
3. 循环遍历辅助栈中的元素，逐个累加得到总得分值。

​ ⭐️为了进一步提高算法效率，步骤③中循环遍历的累加操作可直接在步骤②遍历时进行。需要注意的是，当遇到记录record为字符串"C"时，应作减操作。

public class Solution {
    public int calPoints(String[] records) {
        int score = 0;
        Deque<String> stack = new ArrayDeque<>();
        for (String record : records) {
            switch (record) {
                case "+": {
                    int sum = Integer.parseInt(stack.peek()) + Integer.parseInt(stack.get(stack.size() - 2));
                    score += sum;
                    stack.push(String.valueOf(sum));
                    break;
                }
                case "D": {
                    int doubleS = Integer.parseInt(stack.peek()) * 2;
                    stack.push(String.valueOf(doubleS));
                    score += doubleS;
                    break;
                }
                case "C": {
                    String cancel = stack.pop();
                    score -= Integer.parseInt(cancel);
                    break;
                }
                default: {
                    stack.push(record);
                    score += Integer.parseInt(record);
                }
            }
        }
        return score;
    }
}

💭 复杂度分析

​ 基于栈 + 模拟的解决方案的复杂度分析如下。

• 时间复杂度：$O(n)$，其中$n$为字符串序列的大小。
• 空间复杂度：$O(n)$。