Medium

题目描述

你正在玩一个视频游戏，需要保卫你的城市免受一群 n 个怪物的攻击。给你一个下标从 0 开始的整数数组 dist，其中 dist[i] 是第 i 个怪物与城市的初始距离（单位：千米）。

怪物以恒定的速度向城市移动。每个怪物的速度在整数数组 speed 中给出，其中 speed[i] 是第 i 个怪物的速度（单位：千米/分钟）。

你有一个武器，一旦完全充电，就可以消灭一个怪物。但是，武器需要一分钟才能充电。武器在最开始就是满电的。

当任何怪物到达你的城市时，你就输了。如果怪物在武器完全充电的那一刻到达城市，这也算作失败，游戏在你能够使用武器之前就结束了。

返回在你失败之前可以消灭的怪物的最大数量，如果你可以在所有怪物到达城市之前消灭它们，则返回 n。

示例 1：

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

示例 2：

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

示例 3：

输入：dist = [3,2,4], speed = [5,3,2]
输出：1
解释：
开始时，怪物的距离分别为 [3,2,4]。你消灭第一个怪物。
一分钟后，怪物的距离分别为 [X,0,2]，所以你失败了。
你只能消灭 1 个怪物。

提示：

  • n == dist.length == speed.length
  • 1 <= n <= 10^5
  • 1 <= dist[i], speed[i] <= 10^5

解题思路

这道题的核心思路是贪心算法。我们需要按照怪物到达城市的时间顺序来消灭它们。

首先计算每个怪物到达城市所需的时间：时间 = 距离 / 速度。注意这里要用上取整，因为怪物在任何时刻到达都算失败。

然后将所有怪物按照到达时间从小到大排序。接下来模拟消灭过程：

  • 第0分钟可以消灭第一个怪物
  • 第1分钟可以消灭第二个怪物
  • …
  • 第i分钟可以消灭第(i+1)个怪物

对于第i个要消灭的怪物，如果它的到达时间小于等于i，说明我们无法在它到达之前消灭它，游戏结束。

时间复杂度主要由排序决定，为O(n log n)。空间复杂度为O(n)用于存储到达时间。

这种贪心策略是最优的，因为我们总是优先消灭最早到达的怪物，这样能最大化我们的存活时间。

代码实现

class Solution {
public:
    int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
        int n = dist.size();
        vector<double> arrivalTime(n);
        
        // 计算每个怪物的到达时间
        for (int i = 0; i < n; i++) {
            arrivalTime[i] = (double)dist[i] / speed[i];
        }
        
        // 按到达时间排序
        sort(arrivalTime.begin(), arrivalTime.end());
        
        // 贪心消灭怪物
        for (int i = 0; i < n; i++) {
            if (arrivalTime[i] <= i) {
                return i;
            }
        }
        
        return n;
    }
};

class Solution:
    def eliminateMaximum(self, dist: List[int], speed: List[int]) -> int:
        n = len(dist)
        
        # 计算每个怪物的到达时间
        arrival_times = []
        for i in range(n):
            arrival_times.append(dist[i] / speed[i])
        
        # 按到达时间排序
        arrival_times.sort()
        
        # 贪心消灭怪物
        for i in range(n):
            if arrival_times[i] <= i:
                return i
        
        return n

public class Solution {
    public int EliminateMaximum(int[] dist, int[] speed) {
        int n = dist.Length;
        double[] arrivalTimes = new double[n];
        
        // 计算每个怪物的到达时间
        for (int i = 0; i < n; i++) {
            arrivalTimes[i] = (double)dist[i] / speed[i];
        }
        
        // 按到达时间排序
        Array.Sort(arrivalTimes);
        
        // 贪心消灭怪物
        for (int i = 0; i < n; i++) {
            if (arrivalTimes[i] <= i) {
                return i;
            }
        }
        
        return n;
    }
}

/**
 * @param {number[]} dist
 * @param {number[]} speed
 * @return {number}
 */
var eliminateMaximum = function(dist, speed) {
    const n = dist.length;
    
    // 计算每个怪物的到达时间
    const arrivalTimes = [];
    for (let i = 0; i < n; i++) {
        arrivalTimes.push(dist[i] / speed[i]);
    }
    
    // 按到达时间排序
    arrivalTimes.sort((a, b) => a - b);
    
    // 贪心消灭怪物
    for (let i = 0; i < n; i++) {
        if (arrivalTimes[i] <= i) {
            return i;
        }
    }
    
    return n;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n log n)
空间复杂度O(n)

时间复杂度：O(n log n)，主要由排序操作决定。 空间复杂度：O(n)，用于存储每个怪物的到达时间。

相关题目