LeetCoding Challenge Oct. 29: Maximize Distance to Closest…

LeetCode October Challenge の 29 日目。

今日の問題は Maximize Distance to Closest Person。

問題の概要

• 一列に並んだ座席の「空席 (0)」「着席 (1)」状況を表す配列が与えられる
• 新たに座ろうとしている人が一人いて、いずれかの空席に座ろうとしている
• すでに座っている人との空席の間隔が最大となるような空席に座ったとして、そのときの最も近くに座っている人との距離を求める

考え方

• 特に難しい問題ではないので、すぐに O(n) の解法が思い浮かびますね… 😇
  • 座席の列の左端・右端 = 配列の先頭・末尾のところだけ気をつければ大丈夫そう
• 具体的なアルゴリズムはこちら
  1. 配列の先頭から連続している空席の数を求める
  2. 同様に、配列の末尾側に連続している空席の数を求める
  3. 上記の先頭・末尾の空席を取り除いた残りの部分配列より、空席の最大の連 (run) を求める
  4. 以下のいずれかのうち最大の値が解となる
     • 配列の先頭から連続している空席の数
     • 配列の末尾に連続している空席の数
     • 部分配列上の最大の連に 1 を加えて 2 で割った値
• 実装して submit → 一発 accept & beats 100% 達成 🎉

コード

class Solution {
    public int maxDistToClosest(int[] seats) {
        int left = 0;
        while (seats[left] == 0) {
            left++;
        }

        int right = seats.length - 1;
        while (seats[right] == 0) {
            right--;
        }

        int maxRun = 0;
        int run = 0;
        for (int i = left + 1; i < right; i++) {
            if (seats[i] == 0) {
                run++;
            } else {
                maxRun = Math.max(maxRun, run);
                run = 0;
            }
        }

        return Math.max(Math.max(left, seats.length - 1 - right), (Math.max(maxRun, run) + 1) / 2);
    }
}