How do I handle the '+' operation in the Baseball Game problem?

The '+' operation requires you to sum the last two scores in the stack. Ensure that there are at least two scores before applying this operation.

Why do I need to use a stack to solve this problem?

A stack is ideal because it allows us to efficiently manage and modify the last few scores, which is central to operations like removing or duplicating the last score.

Can I solve this problem without using a stack?

While it's possible to solve this with other data structures, a stack provides a simple and efficient way to handle the problem's operations in O(N) time and O(N) space.

What is the time and space complexity of this problem?

The time complexity is O(N), where N is the number of operations. The space complexity is O(N) because we store up to N scores in the stack at any point.

How do I handle invalidations when the stack is empty?

Ensure that any operation that removes a score ('C') checks that there is at least one score in the stack to prevent errors.

#682

Easy

auto_awesome栈·状态

LeetCode 题解工作台

棒球比赛

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

数组栈模拟

题目描述

你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。

比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 ops，其中 ops[i] 是你需要记录的第 i 项操作，ops 遵循下述规则：

整数 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

示例 2：

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

示例 3：

输入：ops = ["1"]
输出：1

提示：

1 <= ops.length <= 1000
ops[i] 为 "C"、"D"、"+"，或者一个表示整数的字符串。整数范围是 [-3 * 10⁴, 3 * 10⁴]
对于 "+" 操作，题目数据保证记录此操作时前面总是存在两个有效的分数
对于 "C" 和 "D" 操作，题目数据保证记录此操作时前面总是存在一个有效的分数

lightbulb

解题思路

方法一：栈 + 模拟

我们可以使用栈来模拟这个过程。

遍历 $\textit{operations}$ ，对于每个操作：

如果是 +，则将栈顶两个元素相加，然后将结果入栈；
如果是 D，则将栈顶元素的值乘以 2，然后将结果入栈；
如果是 C，则将栈顶元素出栈；
如果是数字，将数字入栈。

最后，将栈中的所有元素求和即为答案。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为 $\textit{operations}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def calPoints(self, operations: List[str]) -> int:
        stk = []
        for op in operations:
            if op == "+":
                stk.append(stk[-1] + stk[-2])
            elif op == "D":
                stk.append(stk[-1] << 1)
            elif op == "C":
                stk.pop()
            else:
                stk.append(int(op))
        return sum(stk)

speed

复杂度分析

指标	值
时间	O(N)
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates understanding of stack-based state management.
question_mark
Candidate effectively handles the various operations and edge cases (e.g., invalidations, empty stack).
question_mark
Candidate explains the space complexity and how it relates to the number of operations.

warning

常见陷阱

外企场景

error
Misunderstanding the behavior of the '+' operation, which requires at least two previous scores.
error
Failing to properly handle the 'C' operation when the stack is empty.
error
Overcomplicating the space or time complexity when the solution is straightforward with a stack.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Changing the number of operations or limiting the types of operations.
arrow_right_alt
Allowing negative or very large numbers in the score list.
arrow_right_alt
Handling a larger range of invalidation rules, such as invalidating multiple previous scores at once.

help

常见问题

外企场景

继续练习

#735 小行星碰撞 #946 验证栈序列 #1441 用栈操作构建数组