棒球比赛 图解题解

这道题到底在问什么

输入

["5","2","C","D","+"]

输出

30

输入

本节演示 ["5","-2","4","C","D","9","+","+"]

输出

27

先想最直接的笨办法

上方一排是要依次处理的 8 个操作。栈一开始是空的,我们从最左边第一个操作开始,一个一个地按规则维护这个「有效得分栈」。请盯住栈顶,后面三种指令都只在栈顶附近动手。（动画第 4 步）

最优解：一步一步想明白

1. 3记牢「数字入栈、加号压两数之和、D 压翻倍、C 弹栈、最后求和」,下面每一帧都在套它。
2. 4上方一排是要依次处理的 8 个操作。栈一开始是空的,我们从最左边第一个操作开始,一个一个地按规则维护这个「有效得分栈」。请盯住栈顶,后面三种指令都只在栈顶附近动手。
3. 5扫到第 0 个操作,是个整数 5。整数最简单,它就是本回合直接拿到的得分,不依赖前面任何数,直接入栈就行。
4. 6把 5 压进栈,它现在是栈顶,也就是「最近一次得分」。如果后面紧跟着 "D"、"C" 或参与 "+",盯的都是这个 5。继续往后扫第 一 个操作。
5. 7扫到第 1 个操作,是个整数 -2。整数最简单,它就是本回合直接拿到的得分,不依赖前面任何数,直接入栈就行。
6. 8把 -2 压进栈,它现在是栈顶,也就是「最近一次得分」。如果后面紧跟着 "D"、"C" 或参与 "+",盯的都是这个 -2。继续往后扫第 二 个操作。
7. 9扫到第 2 个操作,是个整数 4。整数最简单,它就是本回合直接拿到的得分,不依赖前面任何数,直接入栈就行。
8. 10把 4 压进栈,它现在是栈顶,也就是「最近一次得分」。如果后面紧跟着 "D"、"C" 或参与 "+",盯的都是这个 4。继续往后扫第 三 个操作。
9. 11扫到第 3 个操作,是 "C"。它的含义是「把前一次得分作废、从记录里移除」。前一次得分就是栈顶的 4,接下来要把它弹出去。
10. 12把栈顶的 4 弹出栈,它从此不参与最后的求和。弹完之后,栈顶回到了它下面那个数,后续的指令都以这个新栈顶为「上一次得分」。
11. 13扫到第 4 个操作,是 "D"。它的含义是「本次得分等于前一次得分的两倍」。前一次得分就是栈顶的 -2,把它翻倍就是新得分。
12. 14-2 乘 2 等于 -4,把这个新得分 -4 压进栈。原来的 -2 不受影响,它还是有效得分。栈顶现在变成了 -4。
13. 15扫到第 5 个操作,是个整数 9。整数最简单,它就是本回合直接拿到的得分,不依赖前面任何数,直接入栈就行。
14. 16把 9 压进栈,它现在是栈顶,也就是「最近一次得分」。如果后面紧跟着 "D"、"C" 或参与 "+",盯的都是这个 9。继续往后扫第 六 个操作。
15. 17扫到第 6 个操作,是 "+"。它的含义是「本次得分等于前两次得分之和」。前两次得分就是栈顶的两个数:最上面是 9,往下一个是 -4。把它们加起来就是新得分。
16. 189 加 -4 等于 5,把这个新得分 5 压进栈。注意原来的 9 和 -4 都还在,它们仍是有效得分,只是上面又多压了一个 5。继续看下一个操作。
17. 19扫到第 7 个操作,是 "+"。它的含义是「本次得分等于前两次得分之和」。前两次得分就是栈顶的两个数:最上面是 5,往下一个是 9。把它们加起来就是新得分。
18. 205 加 9 等于 14,把这个新得分 14 压进栈。注意原来的 5 和 9 都还在,它们仍是有效得分,只是上面又多压了一个 14。继续看下一个操作。
19. 218 个操作全部处理完,栈里现在剩下 5、-2、-4、9、5、14 这 6 个有效得分。被 "C" 作废的那个 4 早就弹掉了,不在里面。最后一步,把栈里这些数全加起来就是答案。
20. 22从左往右把栈里的得分依次加起来。加上第 0 个 5 之后,running 从 0 变成 5。继续加下一个。
21. 23从左往右把栈里的得分依次加起来。加上第 1 个 -2 之后,running 从 5 变成 3。继续加下一个。
22. 24从左往右把栈里的得分依次加起来。加上第 2 个 -4 之后,running 从 3 变成 -1。继续加下一个。
23. 25从左往右把栈里的得分依次加起来。加上第 3 个 9 之后,running 从 -1 变成 8。继续加下一个。
24. 26从左往右把栈里的得分依次加起来。加上第 4 个 5 之后,running 从 8 变成 13。继续加下一个。
25. 27从左往右把栈里的得分依次加起来。加上第 5 个 14 之后,running 从 13 变成 27。全部加完,总和就是 27,这就是最终答案。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
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] * 2)
            elif op == "C":
                stk.pop()
            else:
                stk.append(int(op))
        return sum(stk)

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int calPoints(vector<string>& operations) {
        vector<int> stk;
        for (auto& op : operations) {
            int n = stk.size();
            if (op == "+") {
                stk.push_back(stk[n - 1] + stk[n - 2]);
            } else if (op == "D") {
                stk.push_back(stk[n - 1] * 2);
            } else if (op == "C") {
                stk.pop_back();
            } else {
                stk.push_back(stoi(op));
            }
        }
        return accumulate(stk.begin(), stk.end(), 0);
    }
};

import java.util.*;
class Solution {
    public int calPoints(String[] operations) {
        Deque<Integer> stk = new ArrayDeque<>();
        for (String op : operations) {
            if ("+".equals(op)) {
                int a = stk.pop();
                int b = stk.peek();
                stk.push(a);
                stk.push(a + b);
            } else if ("D".equals(op)) {
                stk.push(stk.peek() * 2);
            } else if ("C".equals(op)) {
                stk.pop();
            } else {
                stk.push(Integer.valueOf(op));
            }
        }
        return stk.stream().mapToInt(Integer::intValue).sum();
    }
}

复杂度

面试官可能追问