1921. Eliminate Maximum Number of Monsters

解法已隱藏 — 先讀題目敘述、自己想想看，再點上方按鈕揭曉。

1921Eliminate Maximum Number of MonstersGreedyMediumGreedy

有 n 個怪物正向城市靠近。第 i 個怪物距離 dist[i]，速度 speed[i]。你有一把武器，每分鐘初可以消滅一個怪物（第 0 分鐘消滅第一個）。如果任何怪物到達城市則遊戲結束。回傳最多能消滅幾個怪物。

Example:

Input: dist = [1,3,4], speed = [1,1,1] Output: 3

Intuition

TIP

計算每個怪物的到達時間，貪心優先消滅最早到的。

每個怪物的到達時間 = ceil(dist[i] / speed[i])
排序到達時間，第 i 個消滅的怪物必須在第 i 分鐘之前到達（即到達時間 > i）
一旦某個怪物的到達時間 <= 當前分鐘，遊戲結束

Approaches

1. Greedy + Sort — O(n log n) / O(n)

Idea: 計算到達時間並排序，依序消滅，直到有怪物在消滅前到達。
Time: O(n log n)
Space: O(n)

class Solution {
    fun eliminateMaximum(dist: IntArray, speed: IntArray): Int {
        val n = dist.size
        val arrivalTimes = IntArray(n) { i ->
            (dist[i] + speed[i] - 1) / speed[i] // 向上取整
        }
        arrivalTimes.sort()

        for (i in 0 until n) {
            if (arrivalTimes[i] <= i) return i
        }
        return n
    }
}

⭐ 2. As Above (optimal) — O(n log n) / O(n)

Idea: 此題的貪心排序就是最優解，沒有更快的做法。
Time: O(n log n)
Space: O(n)

class Solution {
    fun eliminateMaximum(dist: IntArray, speed: IntArray): Int {
        val arrivals = IntArray(dist.size) { (dist[it] - 1) / speed[it] + 1 }
        arrivals.sort()
        for (i in arrivals.indices) {
            if (arrivals[i] <= i) return i
        }
        return arrivals.size
    }
}

🔑 Takeaways

Pattern: 排序 + 貪心 — 最緊急的先處理
Key trick: 向上取整 ceil(a/b) = (a + b - 1) / b 或 (a - 1) / b + 1；排序到達時間後逐一比較即可

Intuition

Approaches

🔑 Takeaways

相關題目