本文介绍一种基于最大堆的贪心策略，解决“在多个工厂中安装最少数量滤网以使总污染减半”的经典面试题，时间复杂度优化至 o(k log n)，适用于大规模输入。
本文介绍一种基于最大堆的贪心策略，解决“在多个工厂中安装最少数量滤网以使总污染减半”的经典面试题，时间复杂度优化至 o(k log n)，适用于大规模输入。
该问题本质是：给定一组非负整数表示各工厂初始污染值，每安装一个滤网可将某一个工厂的当前污染值减半（支持多次安装于同一工厂），目标是使所有工厂污染总和 ≤ 初始总和的一半，并求所需滤网的最小数量。
直观来看，每次应优先对当前污染值最高的工厂安装滤网——因为减半操作带来的绝对削减量最大（例如 18→9 减少 9，而 3→1.5 仅减少 1.5）。这一贪心选择具有最优子结构性质，可通过最大堆（PriorityQueue）高效维护动态最大值。
以下是 Java 实现的核心逻辑：
import java.util.*;
public static int getMinimumFilters(double[] pollutionLevels) {
double currentPollution = Arrays.stream(pollutionLevels).sum();
double targetPollution = currentPollution / 2.0;
// 使用最大堆（逆序优先队列）维护当前各工厂污染值
PriorityQueue<double> maxHeap = new PriorityQueue(Collections.reverseOrder());
for (double level : pollutionLevels) {
maxHeap.offer(level);
}
int numFilters = 0;
while (currentPollution > targetPollution) {
double maxPollution = maxHeap.poll(); // 取出当前最大污染值
double reduced = maxPollution / 2.0; // 安装滤网后的新值
maxHeap.offer(reduced); // 将减半后的值重新入堆
currentPollution -= reduced; // 总污染减少量 = 原值 - 新值 = maxPollution/2
numFilters++;
}
return numFilters;
}</double>
关键点解析：
- ✅ 贪心正确性：每次削减当前最大值的一半，等价于获得最大可能的单次污染降低量，确保全局步数最少；
- ✅ 堆结构优势：PriorityQueue（底层为二叉堆）支持 O(log n) 插入与删除，避免了每次线性扫描找最大值；
- ⚠️ 精度注意：题目允许浮点运算，但若输入为整数且要求严格整数输出（如最终结果需向上取整），需额外处理边界情况（本题示例中 16.5 为精确目标，直接比较 > 即可）；
- ⚠️ 边界处理：当 pollutionLevels 为空或全零时，currentPollution 为 0，循环不执行，返回 0，符合语义。
运行示例：
输入 [3, 5, 6, 1, 18] → 初始总和 33，目标 16.5
- 第1次：取 18 → 变 9，总和变为 33 − 9 = 24
- 第2次：取 9 → 变 4.5，总和变为 24 − 4.5 = 19.5
- 第3次：取 6 → 变 3，总和变为 19.5 − 3 = 16.5 → 达标，返回 3
该解法时间复杂度为 O(k log n)（k 为滤网数，最坏 k ≤ 30,000 × log₂(70,000) ≈ 500,000），空间复杂度 O(n)，完全满足题目对规模 [1..30,000] 的要求，是面试中推荐的标准解法。
