Problem#
一條路上有 $n$ 台車，每台車可以有三種方向: S, L, R 分別是靜止、左、右。今天每台車都朝其方向駛去，當相撞時車子留在原地，問你給定一個 directions 序列，有幾台車會撞車。
想法#
可以觀察到 RS, SL, RL 這三種狀況一定會撞到，但如果序列是 RRL 則最一開始的 R 不會算到，所以必須要記錄 R 的數量，當遇到前面三種撞車的狀況時，就將目前算到 `R 的數量也加到答案中(那些 R 的車也會撞到)
- 時間複雜度: $\mathcal{O}(n)$
- 空間複雜度: $\mathcal{O}(1)$
AC Code#
賞析#
- 因為我們只在乎撞車的數量，所以只要找最左邊的
R和最右邊的L，在這之間的所有L和R最後都一定會相撞
心得#
賽中沒想到要把撞到的車改成 S，然後計算沒相撞時 R 的數量，真的要多寫 greedy 的題目