1921. Eliminate Maximum Number of Monsters

Medium
Description

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

Example:

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

Intuition#

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

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

Approaches#

1: 貪心 + 排序#

  • 概念: 計算到達時間並排序，依序消滅，直到有怪物在消滅前到達。
  • 時間複雜度: O(n log n)
  • 空間複雜度: 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: 同上（最優解）#

  • 概念: 此題的貪心排序就是最優解，沒有更快的做法。
  • 時間複雜度: O(n log n)
  • 空間複雜度: 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: 排序 + 貪心 — 最緊急的先處理
  • 關鍵技巧: 向上取整 ceil(a/b) = (a + b - 1) / b 或 (a - 1) / b + 1；排序到達時間後逐一比較即可