You are playing a video game where you are defending your city from a group of n
monsters. You are given a 0-indexed integer array dist
of size n
, where dist[i]
is the initial distance in kilometers of the ith
monster from the city.
The monsters walk toward the city at a constant speed. The speed of each monster is given to you in an integer array speed
of size n
, where speed[i]
is the speed of the ith
monster in kilometers per minute.
You have a weapon that, once fully charged, can eliminate a single monster. However, the weapon takes one minute to charge.The weapon is fully charged at the very start.
You lose when any monster reaches your city. If a monster reaches the city at the exact moment the weapon is fully charged, it counts as a loss, and the game ends before you can use your weapon.
Return the maximum number of monsters that you can eliminate before you lose, or n
if you can eliminate all the monsters before they reach the city.
Example 1:
Input: dist = [1,3,4], speed = [1,1,1] Output: 3 Explanation: In the beginning, the distances of the monsters are [1,3,4]. You eliminate the first monster. After a minute, the distances of the monsters are [X,2,3]. You eliminate the second monster. After a minute, the distances of the monsters are [X,X,2]. You eliminate the thrid monster. All 3 monsters can be eliminated.
Example 2:
Input: dist = [1,1,2,3], speed = [1,1,1,1] Output: 1 Explanation: In the beginning, the distances of the monsters are [1,1,2,3]. You eliminate the first monster. After a minute, the distances of the monsters are [X,0,1,2], so you lose. You can only eliminate 1 monster.
Example 3:
Input: dist = [3,2,4], speed = [5,3,2] Output: 1 Explanation: In the beginning, the distances of the monsters are [3,2,4]. You eliminate the first monster. After a minute, the distances of the monsters are [X,0,2], so you lose. You can only eliminate 1 monster.
Constraints:
n == dist.length == speed.length
1 <= n <= 105
1 <= dist[i], speed[i] <= 105
消灭怪物的最大数量。
你正在玩一款电子游戏,在游戏中你需要保护城市免受怪物侵袭。给你一个 下标从 0 开始 且长度为
n
的整数数组dist
,其中dist[i]
是第i
个怪物与城市的 初始距离(单位:米)。怪物以 恒定 的速度走向城市。给你一个长度为
n
的整数数组speed
表示每个怪物的速度,其中speed[i]
是第i
个怪物的速度(单位:米/分)。怪物从 第 0 分钟 时开始移动。你有一把武器,并可以 选择 在每一分钟的开始时使用,包括第 0 分钟。但是你无法在一分钟的中间使用武器。这种武器威力惊人,一次可以消灭任一还活着的怪物。
一旦任一怪物到达城市,你就输掉了这场游戏。如果某个怪物 恰 在某一分钟开始时到达城市,这会被视为 输掉 游戏,在你可以使用武器之前,游戏就会结束。
返回在你输掉游戏前可以消灭的怪物的 最大 数量。如果你可以在所有怪物到达城市前将它们全部消灭,返回
n
。
思路是贪心,具体做法是排序。因为有了怪物的距离和速度,那么我们可以得到一个 time 数组,记录每个怪物到达城市所需要的时间。这里注意需要用 double 型记录。time 数组创建好了之后我们将他排序,时间较早的排在前面。然后遍历 time 数组,我们用下标模拟时间的流逝,如果 time[i] > i (下标),说明我们可以在这个怪物未到达之间就消灭他;反之就不行,就可以立即 break 了。
时间O(nlogn)
空间O(1)
Java实现
1 class Solution { 2 public int eliminateMaximum(int[] dist, int[] speed) { 3 int n = dist.length; 4 double[] time = new double[n]; 5 for (int i = 0; i < n; i++) { 6 time[i] = (double) dist[i] / speed[i]; 7 } 8 9 Arrays.sort(time); 10 // System.out.println(Arrays.toString(time)); 11 int count = 0; 12 for (int i = 0; i < n; i++) { 13 if ((double) i < time[i]) { 14 count++; 15 } else { 16 break; 17 } 18 } 19 return count == n ? n : count; 20 } 21 }
- Eliminate LeetCode Monsters Maximum Numbereliminate leetcode monsters maximum consecutive maximum number values the maximum reached number maximum number array pairs performance leetcode maximum 1383 leetcode detonate maximum bombs leetcode maximum binary depth maximum-product-subarray leetcode subarray maximum subarrays leetcode distinct maximum leetcode integers positive maximum