682. 棒球比赛

🎯 问题描述

描述：
你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。
比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 operations，其中 operations[i] 是你需要记录的第 i 项操作，遵循下述规则：

整数 x：表示本回合新获得分数 x。
“+”：表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。
“D”：表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。
“C”：表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。

请你返回记录中所有得分的总和。

说明：

这是一个典型的栈应用问题。
核心策略：
- 我们需要维护一个记录所有有效得分的列表（栈）。
- 对于每种操作，根据栈顶（最近一次得分）或次栈顶（倒数第二次得分）的元素进行计算或修改。
- 最后对栈中所有元素求和。
示例：
示例 1：

输入：ops = ["5","2","C","D","+"]
输出：30
解释：
"5" - 记录加 5 ，记录现在是 [5]
"2" - 记录加 2 ，记录现在是 [5, 2]
"C" - 使前一次得分的记录无效并将其移除，记录现在是 [5]
"D" - 记录加 2 * 5 = 10 ，记录现在是 [5, 10]
"+" - 记录加 5 + 10 = 15 ，记录现在是 [5, 10, 15]
所有得分的总和 5 + 10 + 15 = 30

💻 解题思路

思路1：栈模拟

核心逻辑

初始化：
- 创建一个空列表 ans 作为栈，用来存储每一轮的有效得分。
遍历操作：
- 遍历 operations 中的每一个操作 ops。
- 情况 A：“+”
  - 新得分 = 栈顶元素 + 次栈顶元素 (ans[-1] + ans[-2])。
  - 将新得分压入栈。
- 情况 B：“D”
  - 新得分 = 栈顶元素 * 2 (2 * ans[-1])。
  - 将新得分压入栈。
- 情况 C：“C”
  - 撤销上一轮得分，弹出栈顶元素 (ans.pop())。
- 情况 D：整数 x
  - 将字符串转换为整数 (int(ops))，并压入栈。
计算结果：
- 遍历结束后，返回 ans 中所有元素的和 (sum(ans))。

代码实现

class Solution:
    def calPoints(self, operations: List[str]) -> int:
        ans = []  # 使用列表作为栈来存储有效分数
        
        for ops in operations:
            if ops == "+":
                # 新得分是前两次得分的总和
                ans.append(ans[-1] + ans[-2])
            elif ops == "D":
                # 新得分是前一次得分的两倍
                ans.append(2 * ans[-1])
            elif ops == "C":
                # 前一次得分无效，移除之
                ans.pop()
            else:
                # 整数 x，直接入栈
                ans.append(int(ops))
                
        # 返回所有有效得分的总和
        return sum(ans)

📊 性能分析

时间复杂度： $O(N)$ $O (N)$
- 其中 $N$ 是 operations 的长度。
- 我们只需要遍历一次操作列表，每次操作（入栈、出栈、加法、乘法）都是 $O(1)$ 的。
- 最后的 sum(ans) 也是 $O(N)$ ，总体保持线性。
空间复杂度： $O(N)$ $O (N)$
- 我们需要一个栈来存储有效得分。
- 在最坏情况下（没有 “C” 操作），栈的大小等于操作次数 $N$ 。

思考

为什么使用栈？
- 题目中的操作具有“后进先出”的特性。
- 特别是 “C” 操作（撤销上一轮）和 “D”、“+” 操作（依赖上一轮或上两轮），都直接指向最近的历史记录。栈是管理这种“最近历史”最自然的数据结构。
Python 列表的特性：
- 在 Python 中，列表（List）不仅支持索引访问，其 append() 和 pop() 方法的时间复杂度均为 $O(1)$ ，非常适合作为栈使用。
- ans[-1] 和 ans[-2] 的负数索引语法让获取栈顶元素变得非常简洁。
为什么不使用变量模拟？
- 有些初学者可能会尝试用 pre1（上一轮得分）和 pre2（上上轮得分）两个变量来模拟。
- 这种方法在处理连续的 “C” 操作时会失效，因为变量无法保存完整的历史记录（例如，撤销后再撤销，需要知道更早之前的得分）。栈则完美解决了这个问题，因为它保存了所有历史有效状态。
数据转换：
- 输入是字符串列表，对于数字操作，必须使用 int() 函数进行转换。
- 题目保证了操作的有效性（例如执行 “+” 时前面一定有两个分数），所以代码中不需要额外的边界检查。