你正在記錄棒球比賽的分數，給定一系列操作字串
ops：
- 整數
x：記錄新分數x"+"：記錄前兩次分數之和"D"：記錄前一次分數的兩倍"C"：移除前一次的分數回傳所有分數的總和。
Example:
Input: ops = [“5”,“2”,“C”,“D”,”+”] Output: 30
Intuition
TIP
核心思路：用堆疊模擬每一步操作，最後對堆疊中所有元素求和。
- 操作本質上就是「往記錄末尾新增」或「移除末尾」，完全符合堆疊 LIFO 特性
"C"對應 pop，"D"和"+"需要 peek 前面的元素再 push 新值
Approaches
1. Array as Stack (no boxing) — O(n) / O(n)
- Idea: 用
IntArray+ 寫入指標當堆疊，避免ArrayDeque<Int>的裝箱開銷 - Time:
O(n) - Space:
O(n)
class Solution {
fun calPoints(operations: Array<String>): Int {
val scores = IntArray(operations.size)
var size = 0
for (op in operations) {
when (op) {
"C" -> size--
"D" -> { scores[size] = scores[size - 1] * 2; size++ }
"+" -> { scores[size] = scores[size - 1] + scores[size - 2]; size++ }
else -> { scores[size] = op.toInt(); size++ }
}
}
var sum = 0
for (i in 0 until size) sum += scores[i]
return sum
}
}⭐ 2. Stack Simulation — O(n) / O(n)
- Idea: 遍歷操作陣列，依據每個操作類型對堆疊做對應處理，最後加總
- Time:
O(n)- 遍歷一次操作陣列 - Space:
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: 需要「回溯/撤銷最近操作」的模擬題，堆疊是最自然的選擇
- Key trick:
"+"操作需要存取前兩個元素，先 pop 再 peek 再 push 回去即可