1921. 消灭怪物的最大数量

• 标签：贪心、数组、排序
• 难度：中等

题目链接

• 1921. 消灭怪物的最大数量 - 力扣

题目大意

描述：你正在玩一款电子游戏，在游戏中你需要保护城市免受怪物侵袭。给定一个下标从 $0$ 开始且大小为 $n$ 的整数数组 $dist$，其中 $dist[i]$ 是第 $i$ 个怪物与城市的初始距离（单位：米）。

怪物以恒定的速度走向城市。每个怪物的速度都以一个长度为 $n$ 的整数数组 $speed$ 表示，其中 $speed[i]$ 是第 $i$ 个怪物的速度（单位：千米/分）。

你有一种武器，一旦充满电，就可以消灭 一个 怪物。但是，武器需要 一分钟 才能充电。武器在游戏开始时是充满电的状态，怪物从 第 $0$ 分钟时开始移动。

一旦任一怪物到达城市，你就输掉了这场游戏。如果某个怪物 恰好 在某一分钟开始时到达城市（距离表示为 $0$），这也会被视为输掉 游戏，在你可以使用武器之前，游戏就会结束。

要求：返回在你输掉游戏前可以消灭的怪物的最大数量。如果你可以在所有怪物到达城市前将它们全部消灭，返回 $n$。

说明：

示例：

• 示例 1：

输入：dist = [1,3,4], speed = [1,1,1]
输出：3
解释：
第 0 分钟开始时，怪物的距离是 [1,3,4]，你消灭了第一个怪物。
第 1 分钟开始时，怪物的距离是 [X,2,3]，你消灭了第二个怪物。
第 3 分钟开始时，怪物的距离是 [X,X,2]，你消灭了第三个怪物。
所有 3 个怪物都可以被消灭。

• 示例 2：

输入：dist = [1,1,2,3], speed = [1,1,1,1]
输出：1
解释：
第 0 分钟开始时，怪物的距离是 [1,1,2,3]，你消灭了第一个怪物。
第 1 分钟开始时，怪物的距离是 [X,0,1,2]，所以你输掉了游戏。
你只能消灭 1 个怪物。

解题思路

思路 1：排序 + 贪心算法

对于第 $i$ 个怪物，最晚可被消灭的时间为 $times[i] = \lfloor \frac{dist[i] - 1}{speed[i]} \rfloor$。我们可以根据以上公式，将所有怪物最晚可被消灭时间存入数组 $times$ 中，然后对 $times$ 进行升序排序。

然后遍历数组 $times$，对于第 $i$ 个怪物：

1. 如果 $times[i] < i$，则说明第 $i$ 个怪物无法被消灭，直接返回 $i$ 即可。
2. 如果 $times[i] \ge i$，则说明第 $i$ 个怪物可以被消灭，继续向下遍历。

如果遍历完数组 $times$，则说明所有怪物都可以被消灭，则返回 $n$。

思路 1：代码

class Solution:
    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:
        times = []
        for d, s in zip(dist, speed):
            time = (d - 1) // s
            times.append(time)
        times.sort()

        size = len(times)
        for i in range(size):
            if times[i] < i:
                return i

        return size

思路 1：复杂度分析

• 时间复杂度：$O(n \times \log n)$，其中 $n$ 为数组 $dist$ 的长度。
• 空间复杂度：$O(n)$。