付費限定文章

堆疊應用+模擬: 星球碰撞_Leetcode 精選75題解析

Chris Henry on Unsplash

題目敘述

題目會給定我們一個整數陣列asteroids，每個元素代表每顆星球的大小和飛行方向。

絕對值的部分越大，代表星球的大小越大。

若數值為正，代表星球向右飛。

若數值為負，代表星球向左飛。

當兩顆星球碰撞時，會有以下碰撞規則規定:

如果一顆比較大，另一顆比較小，則比較大的那棵存活，並且繼續飛行；比較小的那棵則被消滅。

如果兩顆一樣大，則兩顆一起被消滅。

請問最後存活的是哪幾顆星球，動態為何?以陣列的形式輸出答案。

題目的原文敘述

測試範例

Example 1:

Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.
-5 和 10 碰撞後，10比較大顆，-5比較小顆，10這棵存活，-5這顆被消滅，​

Example 2:

Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.
8 和 -8碰撞後，兩顆一樣大，一起被消滅。

Example 3:

Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.
2​ 和 -5 碰撞後，-5​比較大顆，2比較小顆，-5這棵存活，2這顆被消滅，​
-5​ 和 10 碰撞後，10​比較大顆，-5比較小顆，10這棵存活，-5這顆被消滅，​

約束條件

Constraints:

• 2 <= asteroids.length <= 10^4

輸入陣列asteroids長度介於2~10^4之間。

• -1000 <= asteroids[i] <= 1000

每顆星球的數值介於-1000 ~ 1000之間

• asteroids[i] != 0