当前位置：首页 > article >正文

1921.消灭怪物的最大数量

article 2025/3/31 20:49:18

1921. 消灭怪物的最大数量

题目来源：力扣

dist：距离 speed：速度

解题方法：贪心+排序

求消灭怪物最带的数量：

先消灭到达时间早的
用贪心的思路将到达时间排序（得出消灭顺序）
将攻击时间顺序与排序后的怪物到达时间进行比较

代码如下：

class Solution {
     public int eliminateMaximum(int[] dist, int[] speed) {
         int n = dist.length;
         int[] arrivalTimes = new int[n];
         for (int i = 0; i < n; i++) {
             arrivalTimes[i] = (dist[i] - 1) / speed[i] + 1;
         }
         Arrays.sort(arrivalTimes);
         for (int i = 0; i < n; i++) {
             if (arrivalTimes[i] <= i) {
                 return i;
             }
         }
         return n;
     }
 }

代码逻辑

初始化：
- 代码接收两个整数数组 dist 和 speed 作为输入，分别表示每个怪物的初始距离和移动速度。
- n 表示怪物的数量，即数组的长度。
- 创建一个长度为 n 的整数数组 arrivalTimes，用于存储每个怪物到达你的时间。
计算到达时间：
- 通过一个 for 循环遍历每个怪物，计算其到达时间。
- 到达时间的计算公式为 (dist[i] - 1) / speed[i] + 1，这是因为怪物到达你时，其移动的距离至少为 dist[i]，使用 (dist[i] - 1) / speed[i] + 1 可以确保计算出的是整数时间。
对到达时间排序：
- 使用 Arrays.sort(arrivalTimes) 对 arrivalTimes 数组进行排序，以便按照怪物到达的先后顺序处理。
检查可消灭的怪物数量：
- 再次使用 for 循环遍历排序后的 arrivalTimes 数组。
- 对于每个怪物，如果其到达时间 arrivalTimes[i] 小于等于当前时间 i（因为每秒可以消灭一个怪物，所以 i 表示当前时间），说明该怪物在你消灭它之前就已经到达，此时返回 i，表示最多能消灭 i 个怪物。
- 如果所有怪物都能在到达之前被消灭，则返回 n，表示可以消灭所有怪物。

复杂度分析

时间复杂度：O(nlogn)，其中 n 是怪物的数量。主要时间开销在于对 arrivalTimes 数组进行排序，排序的时间复杂度为 O(nlogn)，而计算到达时间和检查可消灭的怪物数量的时间复杂度均为 O(n)。
空间复杂度：O(n)，主要空间开销在于创建了一个长度为 n 的 arrivalTimes 数组。