Asteroid Collision
小惑星の列が、すべて同じ速度で一直線に進んでいます。asteroids の各値は1つの小惑星を表します。絶対値は大きさを、符号は進行方向を示し、正の値は右、負の値は左を表します。
右に進む小惑星が左に進む小惑星と出会うと、衝突します。小さい方は爆発し、同じ大きさなら両方とも爆発します。同じ方向に進む小惑星同士が出会うことはありません。すべての衝突の後に残った小惑星を、元の順序で返してください。結果は空の場合もあります。
関数
- asteroidsinteger-array
- 小惑星は左から右へ、方向は符号で、大きさは絶対値で
- 戻り値integer-array
- 左から右へ並んだ、残存する小惑星（存在しない場合もある）
制約
1 ≤ asteroids.length ≤ 104-1000 ≤ asteroids[i] ≤ 1000asteroids[i] ≠ 0
例
- 入力
- asteroids = [4, 9, -6, 2, -3]
- 出力
- [4, 9]
- 説明
- 9 は -6 とぶつかって勝ちます。2 は -3 とぶつかって爆発し、その後 -3 は 9 に向かって飛んでいき、同じく爆発します。他に何も動いて何かに向かうことはないので、4 と 9 が残ります。
- 入力
- asteroids = [6, -6]
- 出力
- []
- 説明
- 6 と -6 は同じ大きさでクラッシュするため、両方とも爆発し、結果は空になります。
- 入力
- asteroids = [-2, -7, 3, 8]
- 出力
- [-2, -7, 3, 8]
- 説明
- -2 と -7 は左へ飛び、3 と 8 は右へ飛ぶので、2つのグループは離れていきます。衝突することはなく、4つの小惑星はすべて残ります。
発展問題
スタックは、どの小惑星が生き残るかを答えます。爆発する小惑星についても、それぞれを破壊した小惑星のインデックスを報告するには、どうすればよいでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
衝突が起こるには、左側に右向きに移動する天体があり、右側に左向きに移動する天体が必要です。その前に右向きに移動する天体がない左向きの小惑星は、永久に安全です。行を左から右へ見ていきましょう。新たに現れた左向きの天体は、それより前にあるどの小惑星とまだ衝突する可能性があるでしょうか？
新しい左向きのものは、最も近くに残っている右向きのものに最初に衝突し、次にその隣のものに衝突します。このように、爆発するか、右向きのものがなくなるまで続きます。ここまで残ったものはスタックのように振る舞い、次に衝突するのは最も新しいものだけです。
生き残ったものをスタックに保持します。右向きに進むものはすべてプッシュします。左向きに進むものについては、スタックの一番上がより小さい右向きのものなら、ポップします。一番上が同じ大きさの右向きのものなら、それをポップして、新しいものは破棄します。一番上がより大きいなら、新しいものを破棄します。それ以外の場合は、プッシュします。
解説
左向きに進む小惑星1つで、右向きに進む小惑星の長い列を破壊でき、衝突のたびに次に衝突する新しいペアが現れることがあります。新しい小惑星は常に、直近の生存者と最初に出会うため、生存者をスタックに積めば、1回の走査ですべての衝突を処理できます。
クラッシュを一度に1つずつ解決する
正しいが、最大のテストでは終わらない
考え方
2つの小惑星が衝突するのは、右向きの小惑星のすぐ左に左向きの小惑星があるときです。そのようなペアを最初に見つけて衝突を解決し、左からもう一度スキャンします。ペアが残っていなければ、今後衝突は起こらず、その行が答えです。
衝突を解決する順序は関係ありません。隣り合って向かい合う小惑星は、どちらかがほかの何かと衝突する前に互いに衝突します。
衝突のたびに、新たなスキャンと行の中央からの削除が必要です。小さな右向きの小惑星が9,999個続いた後に-1000がある場合、各スキャンでは右向きの小惑星を1つ破壊するために行全体をたどります。ステップ数は約5 × 10^7です。
アルゴリズム
- 小惑星を取り除けるように、行をコピーします。
- 左から順に調べ、
row[i] > 0かつrow[i+1] < 0となる最初のインデックスiを探します。 - 該当するものがなければ、行を返します。
- そうでなければ、小さい方を取り除きます。大きさが等しい場合は両方を取り除き、再び調べます。
def asteroidCollision(asteroids):
row = list(asteroids)
while True:
# A crash happens where a right-mover is directly followed by a left-mover.
hit = -1
for i in range(len(row) - 1):
if row[i] > 0 and row[i + 1] < 0:
hit = i
break
if hit == -1:
return row
right, left = row[hit], -row[hit + 1]
if right > left:
del row[hit + 1]
elif right < left:
del row[hit]
else:
del row[hit:hit + 2]生存者のスタック
考え方
ここまでの生き残りをスタックに保持します。右向きの天体の後ろに左向きの天体が続くことはありません。その組み合わせはすでに衝突しているはずだからです。つまり、衝突を免れた左向きの天体の後に、右向きの天体が続く形になります。
新しい右向きの天体はスタック上のすべての天体から遠ざかるため、スタックに追加します。新しい左向きの天体は、上にある右向きの天体に向かって進み、最も新しい天体と最初に出会うため、次に衝突する可能性があるのはスタックの一番上の天体だけです。最初の例では、-3 は 2 を取り除いた後、9 と衝突して消滅します。スタック [4, 9] が元の順序での答えです。
各天体は高々1回スタックに追加され、高々1回取り除かれるため、1つの左向きの天体が長い連続区間を消し去る場合でも、処理は O(n) です。
アルゴリズム
- 生き残った小惑星の空のスタックから始めます。
- 各小惑星について、右に移動する場合は、それをプッシュして続けます。
- 左に移動する場合は、スタックの一番上にある、それより小さい右向きの小惑星をポップします。
- 一番上が同じ大きさの右向きの小惑星になった場合は、それをポップして新しい小惑星を破棄します。一番上がより大きな右向きの小惑星の場合は、新しい小惑星を破棄します。それ以外の場合は、新しい小惑星をプッシュします。
- スタックを下から上の順に返します。
def asteroidCollision(asteroids):
survivors = [] # the row so far, after every crash it caused
for rock in asteroids:
alive = True
# Only a left-mover can hit something: a right-mover on top of the stack.
while alive and rock < 0 and survivors and survivors[-1] > 0:
top = survivors[-1]
if top < -rock:
survivors.pop() # the right-mover is smaller and explodes
elif top == -rock:
survivors.pop() # same size: both explode
alive = False
else:
alive = False # the right-mover is bigger: the new one explodes
if alive:
survivors.append(rock)
return survivors
落とし穴と境界ケース
- 左向きに進む天体の後に右向きに進む天体が続く場合を衝突とみなすこと。
[-2, -7, 3, 8]ではグループは互いに離れていき、4つすべてが生き残ります。 - 要素を取り出す処理に
whileではなくifを使うこと。[1, 2, 3, 4, 5, -15]では、左向きに進む天体が5つすべての右向きに進む天体を破壊し、生き残ります。 - 大きさが等しい場合を見落とすこと。
[6, -6]では6を取り出し、-6を捨てて、結果を空にしなければなりません。 - 負けた左向きの天体を追加すること。
[9, -6]では-6は爆発するため、スタックに追加してはいけません。まだ生きているかどうかを示すフラグを保持してください。
よくある質問3
Asteroid Collision の時間計算量はどれくらいですか？
残存する天体をスタックで管理するため、時間計算量は O(n)、空間計算量は O(n) です。各天体は最大1回ずつプッシュされ、ポップされます。衝突のたびに列を再走査すると、時間計算量は O(n²) になります。
なぜスタックは Asteroid Collision に適したデータ構造なのでしょうか？
新しい小惑星が到達できるのは最も近くにいる生存者だけで、彼らとは新しい順に出会います。つまり、後入れ先出しです。最後にスタックに残ったものは、もう衝突することがないため、最終的な行になります。
アステロイド衝突は O(1) の追加領域で解けますか？
はい、入力を上書きしてよい場合は可能です。配列の先頭をスタックとして使います。書き込みインデックス top を保持し、asteroids[top-1] と比較して、最初の top 個の要素を返します。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def asteroidCollision(asteroids):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
asteroids = [4, 9, -6, 2, -3]
期待される出力
[4, 9]