Description
你正在記錄棒球比賽的分數，給定一系列操作字串
ops：
- 整數
x：記錄新分數x"+"：記錄前兩次分數之和"D"：記錄前一次分數的兩倍"C"：移除前一次的分數回傳所有分數的總和。
Example:
Input: ops = [“5”,“2”,“C”,“D”,"+"] Output: 30
Intuition#
核心思路：用堆疊模擬每一步操作，最後對堆疊中所有元素求和。
- 操作本質上就是「往記錄末尾新增」或「移除末尾」，完全符合堆疊 LIFO 特性
"C"對應 pop，"D"和"+"需要 peek 前面的元素再 push 新值
Approaches#
⭐1: Stack 模擬#
- 概念: 遍歷操作陣列，依據每個操作類型對堆疊做對應處理，最後加總
- 時間複雜度:
O(n)- 遍歷一次操作陣列 - 空間複雜度:
O(n)- 堆疊最多存 n 個分數
class Solution {
fun calPoints(operations: Array<String>): Int {
val stack = ArrayDeque<Int>()
for (op in operations) {
when (op) {
"C" -> stack.removeLast()
"D" -> stack.addLast(stack.last() * 2)
"+" -> {
val top = stack.removeLast()
val newScore = top + stack.last()
stack.addLast(top)
stack.addLast(newScore)
}
else -> stack.addLast(op.toInt())
}
}
return stack.sum()
}
}🔑 Takeaways#
- Pattern: 需要「回溯/撤銷最近操作」的模擬題，堆疊是最自然的選擇
- 關鍵技巧:
"+"操作需要存取前兩個元素，先 pop 再 peek 再 push 回去即可