LeetCoding Challenge Oct. 21: Asteroid Collision

LeetCode October Challenge の 21 日目。

今日の問題は Asteroid Collision。

問題の概要

• 小惑星の大きさと移動方向 (右/左) を表す int 値が、その小惑星の並びに沿って列挙された配列が与えられる
  • 値の絶対値が大きさを表し、符号が移動方向を表す
  • 正数であれば右に移動することを意味し、負数であれば左に移動する
• 小惑星の移動速度はいずれも同じである
• 移動方向がちょうど対抗する関係にある小惑星があった場合、その小惑星同士は衝突することになり、大きい方の小惑星が残って小さい方は消滅する
  • [8, -4] であれば衝突の後に 8 が残る
  • [4, -8] なら -8 が残る
• 大きさが同じ小惑星が衝突した場合はどちらも消滅する
• 衝突を繰り返えされた結果残る小惑星を列挙する

考え方

• これは… スタックを使うのが妥当かしら 🤔
  • 配列は左から右に走査する
  • 正数は無条件にスタックに積む
  • 負数の場合は、以下のいずれかの条件にたどり着くまでスタックから値を下ろし続ける
    • スタックが空になる
      • この場合は負数をスタックに積む
    • スタックの一番上の値が負数である
      • この場合も負数をスタックに積む
    • スタックの一番上の値が絶対値的に大きい
      • この場合はスタックに積まない
    • スタックの一番上の値が絶対値的に同じ
      • この場合はスタックの一番上の値を下ろし、負数は積まない
  • 配列を走査し終えて、最終的にスタックに残った値たちが回答になる
• まあこんな感じでいけばいいのではないかな？
• Java の java.util.Stack クラスを使うのはパフォーマンス的にちょっとアレな面があるけど、まずはこれをつかって実装してみる
• 実装できた → submit → 一発 accept 🤗
  • Runtime 4ms で Your runtime beats 89.47 % of java submissions.
  • 出だしとしてはまずまず
• 速度性能重視でコードを改善してみよう
  • まず、Stack を使うのを改めたい
  • 代わりに、入力として与えられた配列をスタック代わりに使ってしまうのはどうか？
  • スタックの一番上を表す変数を導入して、それを上げ下げする
  • 回答となる int[] は、Arrays.copyOf(asteroids, スタックのサイズ) でシュッと求められる
    • スタックのサイズはスタックの一番上を指す変数を参考に簡単に求まる
• 実装し直して submit → accept
  • Runtime 1ms で Your runtime beats 100.00 % of java submissions. 達成 🎉

コード

java.util.Stack を利用した素直な実装

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();

        outer:
        for (int asteroid : asteroids) {
            if (asteroid > 0) {
                stack.push(asteroid);
                continue;
            }

            int topVal;
            while (!stack.isEmpty()
                    && (topVal = stack.peek()) > 0) {
                int sum = topVal + asteroid;
                if (sum > 0) {
                    continue outer;
                }

                stack.pop();

                if (sum == 0) {
                    continue outer;
                }
            }

            stack.push(asteroid);
        }

        int[] result = new int[stack.size()];
        for (int i = 0; i < stack.size(); i++) {
            result[i] = stack.get(i);
        }

        return result;
    }
}

入力の配列を利用する実装

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        if (asteroids.length <= 1) {
            return asteroids;
        }

        int top = 0;

        outer:
        for (int i = 1; i < asteroids.length; i++) {
            int asteroid = asteroids[i];
            if (asteroid > 0) {
                asteroids[++top] = asteroid;
                continue;
            }

            while (top >= 0
                    && asteroids[top] > 0) {
                int sum = asteroids[top] + asteroid;
                if (sum > 0) {
                    continue outer;
                }

                top--;

                if (sum == 0) {
                    continue outer;
                }
            }

            asteroids[++top] = asteroid;
        }

        return Arrays.copyOf(asteroids, top + 1);
    }
}