LeetCode 1921 消灭怪物的最大数量Eliminate Maximum Number of Monsters排序贪心与最小堆多语言解法详解【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南围绕 LeetCode 1921「消灭怪物的最大数量」展开完整讲解如何用排序 贪心、原地覆盖数组与最小堆三种思路求解该题并给出 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 九种语言的完整实现与复杂度分析。结合本仓库 cpp/1921-eliminate-maximum-number-of-monsters.cpp、java/1921-eliminate-maximum-number-of-monsters.java、javascript/1921-eliminate-maximum-number-of-monsters.js 等真实解法文件读者读完将能独立写出正确、可 AC 的代码并避开浮点除法、排序遗漏、边界比较等高频陷阱。问题背景与建模本题的题意取自仓库 cpp/1921-eliminate-maximum-number-of-monsters.cpp 顶部注释如下你在玩一个防守城市的游戏有n只怪物正朝城市走来。给定下标从 0 开始的整数数组dist其中dist[i]是第i只怪物与城市的初始距离千米整数数组speed中speed[i]是第i只怪物的速度千米/分钟。你有一把武器充能完成后每次只能消灭一只怪物充能需要 1 分钟且武器在游戏开始时已充满。一旦任何怪物到达城市你就失败若怪物恰好在武器充满的同一时刻到达城市同样算失败游戏在该时刻使用武器之前结束。返回在失败前你能消灭的怪物最大数量若能消灭全部n只返回n。仓库注释还给出了一个示例cpp/1921-eliminate-maximum-number-of-monsters.cpp输入dist [1,3,4], speed [1,1,1] 输出3模拟过程初始距离为[1,3,4]第 0 分钟消灭第 1 只怪物1 分钟后距离变为[X,2,3]消灭第 2 只再 1 分钟后距离变为[X,X,2]消灭第 3 只全部消灭故答案为 3。核心建模第i只怪物到达城市所需分钟数为dist[i] / speed[i]非整数时向上取整因为怪物在整数分钟边界到达。武器每分钟只能开一枪因此问题转化为从第 0 分钟开始逐分钟开枪如何选择开枪顺序才能最大化消灭数量。前置知识在动手写代码之前需要熟悉以下三块基础排序Sorting主解法先把所有怪物的到达时间排序再按紧迫程度逐个处理这是贪心正确性的前提。贪心算法Greedy Algorithms理解总是优先消灭最早到达的怪物是最优策略——因为任何先打远处怪物的方案都可以交换顺序为先打近处怪物而不会更差。最小堆 / 优先队列Min-Heap / Priority Queue替代解法用最小堆按需取出最小到达时间实现同样的处理顺序。解法一排序 贪心推荐直觉武器每开一枪需要 1 分钟充能要最大化消灭数量就必须优先处理即将到达城市的怪物。对每只怪物计算到达时间distance / speed向上取整然后按到达时间升序排序逐分钟贪心消灭。如果在第minute分钟剩余怪物中最早到达者已经到达minute minReach[minute]游戏结束返回已消灭数量。算法步骤对每只怪物计算minReach[i] ceil(dist[i] / speed[i])将minReach升序排序用下标minute从 0 遍历排序后的数组若minute minReach[minute]说明怪物在能开枪之前就已到达返回当前计数否则消灭计数加 1若全部消灭返回总数n。多语言实现class Solution: def eliminateMaximum(self, dist: List[int], speed: List[int]) - int: minReach [math.ceil(d / s) for d, s in zip(dist, speed)] minReach.sort() res 0 for minute in range(len(minReach)): if minute minReach[minute]: return res res 1 return respublic class Solution { public int eliminateMaximum(int[] dist, int[] speed) { int n dist.length; int[] minReach new int[n]; for (int i 0; i n; i) { minReach[i] (int) Math.ceil((double) dist[i] / speed[i]); } Arrays.sort(minReach); int res 0; for (int minute 0; minute n; minute) { if (minute minReach[minute]) { return res; } res; } return res; } }class Solution { public: int eliminateMaximum(vectorint dist, vectorint speed) { int n dist.size(); vectorint minReach(n); for (int i 0; i n; i) { minReach[i] ceil((double)dist[i] / speed[i]); } sort(minReach.begin(), minReach.end()); int res 0; for (int minute 0; minute n; minute) { if (minute minReach[minute]) { return res; } res; } return res; } };class Solution { /** * param {number[]} dist * param {number[]} speed * return {number} */ eliminateMaximum(dist, speed) { let n dist.length; let minReach new Array(n); for (let i 0; i n; i) { minReach[i] Math.ceil(dist[i] / speed[i]); } minReach.sort((a, b) a - b); let res 0; for (let minute 0; minute n; minute) { if (minute minReach[minute]) { return res; } res; } return res; } }public class Solution { public int EliminateMaximum(int[] dist, int[] speed) { int n dist.Length; int[] minReach new int[n]; for (int i 0; i n; i) { minReach[i] (int)Math.Ceiling((double)dist[i] / speed[i]); } Array.Sort(minReach); int res 0; for (int minute 0; minute n; minute) { if (minute minReach[minute]) { return res; } res; } return res; } }func eliminateMaximum(dist []int, speed []int) int { n : len(dist) minReach : make([]int, n) for i : 0; i n; i { minReach[i] (dist[i] speed[i] - 1) / speed[i] } sort.Ints(minReach) res : 0 for minute : 0; minute n; minute { if minute minReach[minute] { return res } res } return res }class Solution { fun eliminateMaximum(dist: IntArray, speed: IntArray): Int { val n dist.size val minReach IntArray(n) { i - (dist[i] speed[i] - 1) / speed[i] } minReach.sort() var res 0 for (minute in 0 until n) { if (minute minReach[minute]) { return res } res } return res } }class Solution { func eliminateMaximum(_ dist: [Int], _ speed: [Int]) - Int { let n dist.count var minReach Int for i in 0..n { minReach[i] (dist[i] speed[i] - 1) / speed[i] } minReach.sort() var res 0 for minute in 0..n { if minute minReach[minute] { return res } res 1 } return res } }impl Solution { pub fn eliminate_maximum(dist: Veci32, speed: Veci32) - i32 { let n dist.len(); let mut min_reach: Veci32 (0..n) .map(|i| (dist[i] speed[i] - 1) / speed[i]) .collect(); min_reach.sort(); let mut res 0; for minute in 0..n { if minute as i32 min_reach[minute] { return res; } res 1; } res } }小提示Go、Kotlin、Swift、Rust 中采用(dist[i] speed[i] - 1) / speed[i]的整数技巧实现向上取整避免了浮点转换C/C/Java/C# 则显式调用ceil。复杂度时间复杂度$O(n \log n)$排序主导遍历为 $O(n)$空间复杂度$O(n)$额外的minReach数组解法二排序 贪心原地覆盖输入数组直觉与解法一逻辑完全相同但复用输入数组dist来存储到达时间省去额外数组的空间。先就地计算到达时间再排序最后逐分钟检查能否在怪物到达前将其消灭。算法步骤用ceil(dist[i] / speed[i])原地覆盖dist[i]将dist升序排序对minute从 0 到n - 1遍历若minute dist[minute]返回minute此时已消灭minute只全部消灭返回n。多语言实现class Solution: def eliminateMaximum(self, dist: List[int], speed: List[int]) - int: for i in range(len(dist)): dist[i] math.ceil(dist[i] / speed[i]) dist.sort() for minute in range(len(dist)): if minute dist[minute]: return minute return len(dist)public class Solution { public int eliminateMaximum(int[] dist, int[] speed) { int n dist.length; for (int i 0; i n; i) { dist[i] (int) Math.ceil((double) dist[i] / speed[i]); } Arrays.sort(dist); for (int minute 0; minute n; minute) { if (minute dist[minute]) { return minute; } } return n; } }class Solution { public: int eliminateMaximum(vectorint dist, vectorint speed) { int n dist.size(); for (int i 0; i n; i) { dist[i] ceil((double)dist[i] / speed[i]); } sort(dist.begin(), dist.end()); for (int minute 0; minute n; minute) { if (minute dist[minute]) { return minute; } } return n; } };class Solution { /** * param {number[]} dist * param {number[]} speed * return {number} */ eliminateMaximum(dist, speed) { let n dist.length; for (let i 0; i n; i) { dist[i] Math.ceil(dist[i] / speed[i]); } dist.sort((a, b) a - b); for (let minute 0; minute n; minute) { if (minute dist[minute]) { return minute; } } return n; } }impl Solution { pub fn eliminate_maximum(mut dist: Veci32, speed: Veci32) - i32 { let n dist.len(); for i in 0..n { dist[i] (dist[i] speed[i] - 1) / speed[i]; } dist.sort(); for minute in 0..n { if minute as i32 dist[minute] { return minute as i32; } } n as i32 } }复杂度时间复杂度$O(n \log n)$空间复杂度$O(1)$ 或 $O(n)$取决于所用排序算法的实现原地排序如堆排序为 $O(1)$库排序可能递归栈 $O(\log n)$ 或归并式 $O(n)$解法三最小堆Min-Heap直觉不必一次性排序全部到达时间可以用最小堆按需取出最小到达时间。每次弹出一个到达时间与当前分钟比较若怪物在开枪前已到达res arrival_time游戏结束否则消灭并计数。处理顺序与排序法完全一致只是把排序换成了堆的按需弹出。算法步骤将每个dist[i] / speed[i]推入最小堆初始化res 0记录消灭数量当堆非空时循环弹出最小到达时间若res arrival_time怪物已到达城市返回res否则res加 1全部消灭后返回res。多语言实现class Solution: def eliminateMaximum(self, dist: List[int], speed: List[int]) - int: minHeap [] for i in range(len(dist)): heapq.heappush(minHeap, dist[i] / speed[i]) res 0 while minHeap: if res heapq.heappop(minHeap): return res res 1 return respublic class Solution { public int eliminateMaximum(int[] dist, int[] speed) { PriorityQueueDouble minHeap new PriorityQueue(); for (int i 0; i dist.length; i) { minHeap.add((double) dist[i] / speed[i]); } int res 0; while (!minHeap.isEmpty()) { if (res minHeap.poll()) { return res; } res; } return res; } }class Solution { public: int eliminateMaximum(vectorint dist, vectorint speed) { priority_queuedouble, vectordouble, greaterdouble minHeap; for (int i 0; i dist.size(); i) { minHeap.push((double)dist[i] / speed[i]); } int res 0; while (!minHeap.empty()) { if (res minHeap.top()) { return res; } minHeap.pop(); res; } return res; } };class Solution { /** * param {number[]} dist * param {number[]} speed * return {number} */ eliminateMaximum(dist, speed) { const minHeap new MinPriorityQueue(); for (let i 0; i dist.length; i) { minHeap.enqueue(dist[i] / speed[i]); } let res 0; while (!minHeap.isEmpty()) { if (res minHeap.dequeue().element) { return res; } res; } return res; } }impl Solution { pub fn eliminate_maximum(dist: Veci32, speed: Veci32) - i32 { let mut min_heap BinaryHeap::new(); for i in 0..dist.len() { // 使用 Reverse 实现最小堆到达时间 dist[i] / speed[i] // 为简化比较这里使用向上取整的整数除法 let arrival (dist[i] speed[i] - 1) / speed[i]; min_heap.push(std::cmp::Reverse(arrival)); } let mut res 0; while let Some(std::cmp::Reverse(arrival)) min_heap.pop() { if res arrival { return res; } res 1; } res } }Rust 的BinaryHeap默认是最大堆需用std::cmp::Reverse包装成最小堆比较时使用向上取整的整数到达时间与其余语言保持一致。复杂度时间复杂度$O(n \log n)$每次 push/pop 为 $O(\log n)$共 $n$ 次空间复杂度$O(n)$堆容量三种解法对比解法核心思路时间复杂度空间复杂度适用场景排序 贪心计算到达时间 → 排序 → 逐分钟消灭$O(n \log n)$$O(n)$最直观推荐首选原地覆盖输入数组复用dist存到达时间再排序$O(n \log n)$$O(1)$视排序实现允许修改输入、追求省空间最小堆按需弹出最小到达时间$O(n \log n)$$O(n)$演示堆的按需提取理解优先队列用法常见陷阱Common Pitfalls陷阱一向下取整而非向上取整计算到达时间必须使用ceil(dist[i] / speed[i])距离 3、速度 2 的怪物在第 2 分钟到达而不是 1.5 分钟。若使用向下取整或直接整数除法会得出错误的到达时间进而导致消灭数量统计错误。陷阱二忘记对到达时间排序贪心策略只有在按到达时间升序处理怪物时才成立。不排序就逐个判断可能先消灭了晚到的怪物而早到的怪物已进入城市得到错误答案。陷阱三比较时的 off-by-one 错误判断条件必须是minute minReach[minute]怪物在当前分钟或更早到达而非minute minReach[minute]。因为每回合在分钟开始时开枪若怪物恰好在第 2 分钟到达、当前也处于第 2 分钟怪物先到游戏结束无法及时开枪。陷阱四浮点与精度解法一/二用ceil转成整数可完全规避浮点误差解法三用dist[i] / speed[i]浮点比较时理论上存在精度风险但题目数据范围内通常无碍。仓库 Java 解法 java/1921-eliminate-maximum-number-of-monsters.java 使用double[] arrivalTime并直接比较arrivalTime[i] i从源码看同样依赖浮点比较若追求绝对稳健建议统一采用向上取整的整数到达时间。仓库源码印证本仓库各语言目录下均有本题的独立实现可作为对照学习材料cpp/1921-eliminate-maximum-number-of-monsters.cpp用vectorfloat存储dist[i] / speed[i]浮点到达时间排序后以time v[i]判断失败注释中标注复杂度为 O(N) 时间、O(N) 空间并附有完整题目描述与示例推演java/1921-eliminate-maximum-number-of-monsters.javadouble[] arrivalTime存浮点到达时间arrivalTime[i] i时break返回计数javascript/1921-eliminate-maximum-number-of-monsters.jsdist.map计算时间、排序后从下标 1 开始比较头部注释标明Greedy | Sorting、$O(n \log n)$ 时间、$O(n)$ 空间kotlin/1921-eliminate-maximum-number-of-monsters.kt用dist.zip(speed)与Math.ceil(...).toInt()计算整数到达时间再排序。对比可见文章解法一/二采用向上取整的整数到达时间 minute minReach[minute]判断仓库实现多采用浮点到达时间 比较两者数学等价只是整数版本彻底规避浮点误差。建议以整数向上取整版本为最终提交代码。总结贪心正确性优先消灭最早到达的怪物必然最优这是本题解法的基石。三种实现排序法额外数组、原地覆盖法省空间、最小堆法按需弹出时间复杂度均为 $O(n \log n)$。边界细节到达时间必须向上取整必须排序失败判断用而非。实战建议首选排序 贪心整数版本简洁、稳健、易解释且可轻松迁移到九种语言。掌握本题后类似的按截止时间调度 / 按紧迫程度贪心问题如会议安排、任务调度类题目都可以复用这套计算时间 → 排序 → 顺序校验的分析框架。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考