消灭怪物的最大数量
难度:
标签:
题目描述
代码结果
运行时间: 99 ms, 内存: 30.1 MB
/*
题目思路:
1. 计算每个怪物到达城市的时间,即dist[i] / speed[i]。
2. 对这些时间进行排序。
3. 从最短的时间开始,每分钟消灭一个怪物,直到无法消灭更多的怪物。
*/
import java.util.Arrays;
public class Solution {
public int eliminateMaximum(int[] dist, int[] speed) {
int n = dist.length;
int[] time = Arrays.stream(dist)
.mapToObj(i -> dist[i])
.mapToInt(i -> (int) Math.ceil((double) dist[i] / speed[i]))
.sorted()
.toArray();
for (int i = 0; i < n; i++) {
if (time[i] <= i) {
return i;
}
}
return n;
}
}
解释
方法:
本题解的核心思路是首先计算每个怪物到达城市的时间,然后根据到达时间进行排序。排序后的数组允许我们按顺序判断每个怪物是否可以在其到达之前被消灭。对于每个怪物,我们检查它的到达时间是否小于或等于我们攻击的时间(即第i分钟对应i号怪物)。如果某个怪物的到达时间小于或等于当前分钟数,游戏结束,返回已消灭的怪物数量。如果所有怪物都可以在到达之前被消灭,则返回怪物总数。
时间复杂度:
O(n log n)
空间复杂度:
O(n)
代码细节讲解
🦆
题解中使用了一个循环来判断怪物是否可以在到达之前被消灭,这种方法在所有怪物速度相同的情况下是否仍然有效?
▷🦆
在考虑边界情况时,如果所有怪物的初始距离都为0,这种情况下题解的逻辑是否仍然适用?
▷