企业官网建设流程全解析

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]），游戏结束，返回已消灭数量。

算法步骤

1. 对每只怪物计算minReach[i] = ceil(dist[i] / speed[i])；
2. 将minReach升序排序；
3. 用下标minute从 0 遍历排序后的数组：
   • 若minute >= minReach[minute]，说明怪物在能开枪之前就已到达，返回当前计数；
   • 否则，消灭计数加 1；
4. 若全部消灭，返回总数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 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.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(vector<int>& dist, vector<int>& speed) { int n = dist.size(); vector<int> 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: Vec<i32>, speed: Vec<i32>) -> i32 { let n = dist.len(); let mut min_reach: Vec<i32> = (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来存储到达时间，省去额外数组的空间。先就地计算到达时间，再排序，最后逐分钟检查能否在怪物到达前将其消灭。

算法步骤

1. 用ceil(dist[i] / speed[i])原地覆盖dist[i]；
2. 将dist升序排序；
3. 对minute从 0 到n - 1遍历：
   • 若minute >= dist[minute]，返回minute（此时已消灭minute只）；
4. 全部消灭，返回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(vector<int>& dist, vector<int>& 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: Vec<i32>, speed: Vec<i32>) -> 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），游戏结束；否则消灭并计数。处理顺序与排序法完全一致，只是把"排序"换成了"堆的按需弹出"。

算法步骤

1. 将每个dist[i] / speed[i]推入最小堆；
2. 初始化res = 0记录消灭数量；
3. 当堆非空时循环：
   • 弹出最小到达时间；
   • 若res >= arrival_time，怪物已到达城市，返回res；
   • 否则res加 1；
4. 全部消灭后返回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 res

public class Solution { public int eliminateMaximum(int[] dist, int[] speed) { PriorityQueue<Double> 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(vector<int>& dist, vector<int>& speed) { priority_queue<double, vector<double>, greater<double>> 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: Vec<i32>, speed: Vec<i32>) -> 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)$（堆容量）

三种解法对比

常见陷阱（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：用vector<float>存储dist[i] / speed[i]浮点到达时间，排序后以time >= v[i]判断失败，注释中标注复杂度为 O(N) 时间、O(N) 空间，并附有完整题目描述与示例推演；
• java/1921-eliminate-maximum-number-of-monsters.java：double[] arrivalTime存浮点到达时间，arrivalTime[i] <= i时break返回计数；
• javascript/1921-eliminate-maximum-number-of-monsters.js：dist.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