leetcode
leetcode 1701 ~ 1750
消灭怪物的最大数量

消灭怪物的最大数量

难度:

标签:

题目描述

代码结果

运行时间: 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,这种情况下题解的逻辑是否仍然适用?
如果所有怪物的初始距离都为0,那么根据题解的逻辑,每个怪物的到达时间会是1分钟(`(0 - 1) // speed + 1 = 1`)。这意味着所有怪物几乎同时在第1分钟到达城市。在这种极端情况下,玩家只能在第0分钟消灭一个怪物,随后在第1分钟时,由于所有剩余怪物同时到达,玩家无法继续消灭更多怪物。因此,题解在这种特殊情况下依然适用,但效果是只能消灭1个怪物,然后游戏结束。

相关问题