682. 棒球比赛

🎯 问题描述

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

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

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

说明：

  • 这是一个典型的栈应用问题。

  • 核心策略：

    • 我们需要维护一个记录所有有效得分的列表（栈）。
    • 对于每种操作，根据栈顶（最近一次得分）或次栈顶（倒数第二次得分）的元素进行计算或修改。
    • 最后对栈中所有元素求和。

  • 示例：

  • 示例 1：

1
2
3
4
5
6
7
8
9
输入：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：栈模拟

核心逻辑

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

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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)
    • 其中 NN 是 operations 的长度。
    • 我们只需要遍历一次操作列表，每次操作（入栈、出栈、加法、乘法）都是 O(1)O(1) 的。
    • 最后的 sum(ans) 也是 O(N)O(N)，总体保持线性。
  • 空间复杂度：O(N)O(N)
    • 我们需要一个栈来存储有效得分。
    • 在最坏情况下（没有 “C” 操作），栈的大小等于操作次数 NN。

思考

  1. 为什么使用栈？

    • 题目中的操作具有“后进先出”的特性。
    • 特别是 “C” 操作（撤销上一轮）和 “D”、“+” 操作（依赖上一轮或上两轮），都直接指向最近的历史记录。栈是管理这种“最近历史”最自然的数据结构。

  2. Python 列表的特性：

    • 在 Python 中，列表（List）不仅支持索引访问，其 append() 和 pop() 方法的时间复杂度均为 O(1)O(1)，非常适合作为栈使用。
    • ans[-1] 和 ans[-2] 的负数索引语法让获取栈顶元素变得非常简洁。

  3. 为什么不使用变量模拟？

    • 有些初学者可能会尝试用 pre1（上一轮得分）和 pre2（上上轮得分）两个变量来模拟。
    • 这种方法在处理连续的 “C” 操作时会失效，因为变量无法保存完整的历史记录（例如，撤销后再撤销，需要知道更早之前的得分）。栈则完美解决了这个问题，因为它保存了所有历史有效状态。

  4. 数据转换：

    • 输入是字符串列表，对于数字操作，必须使用 int() 函数进行转换。
    • 题目保证了操作的有效性（例如执行 “+” 时前面一定有两个分数），所以代码中不需要额外的边界检查。