Problem#
給你一個整數陣列 asteroids 其中的數字正負代表方向(正=右，負=左)，數值的絕對值代表大小
每個小行星沿著各自的方向運動，速度相同。方向相對的發生碰撞；方向相反則永遠不會發生碰撞。發生相撞時大的留下來，小的則消失，如果大小相同則兩個都消失。
問你撞到最後，留下來的有哪些？
測資限制#
- $2 \le n \le 10^4$
- $-1000 \le val \le 1000, val \neq 0$
想法#
用 stack 從左往右掃，當數字 $i > 0$ 且當前 stack 頂端的數字 $< 0$ 時（代表相撞），則判斷大小並推回 stack 中，如果沒有則直接進 stack
掃完一次後可能還沒撞完所有的小行星，當當前陣列裡頭沒有任何 $i > 0, j < 0$ 時則結束
- 時間複雜度: $\mathcal{O}(nk)$
- $k$: 相撞次數
- 空間複雜度: $\mathcal{O}()$
AC Code#
賞析#
官方題解有 $O(n)$ 的做法