- 正确答案：贪心算法解决“用最少数量的箭引爆气球”（LeetCode 452）的核心思路是——将气球按右端点升序排序，然后从左到右遍历，每次选择当前未被射爆气球中右端点最小的那个作为“射箭位置”，一箭射穿所有覆盖该位置的气球；该策略的贪心选择性质在于：在保证覆盖当前最左侧未被覆盖气球的前提下，尽可能让箭的位置靠右（即取其右端点），从而为后续气球留下最大兼容空间。 - 解答思路：第一步：问题建模。每个气球是一个区间 [x_start, x_end]，一支箭在位置 x 可射爆所有满足 x_start ≤ x ≤ x_end 的气球。目标是最小化箭的数量。第二步：贪心选择依据。若不按右端点排序而随意处理，可能过早消耗箭位；反之，优先考虑右端点最小的气球，意味着它“最紧迫”（延伸最短、最容易被遗漏），因此必须在此处或之前射箭；而选它的右端点射箭，是满足“覆盖它”的最靠右合法位置，对后续重叠气球的包容性最强。第三步：扫描维护。设当前箭位置为 arrow_pos，初始为负无穷；遍历排序后气球，若当前气球左端点 > arrow_pos，说明它未被前一箭覆盖，需新增一箭，并将 arrow_pos 更新为其右端点；否则跳过（已被覆盖）。第四步：计数返回。每触发一次“新增箭”，计数器加1。 - 深度知识讲解：【贪心算法的正确性基础】本题贪心策略的可行性依赖两个关键性质：（1）贪心选择性质：存在一个最优解，其中第一支箭射在第一个气球（按右端点排序后）的右端点上。证明：设某最优解中第一箭在 pos < first_ball.end，则可将该箭右移至 first_ball.end，不会导致任何原被射爆气球漏掉（因所有被射气球必满足 start ≤ pos ≤ end，而 pos < end ⇒ start ≤ pos < end ⇒ start ≤ end 仍成立），且可能覆盖更多后续气球，故不劣于原解。（2）最优子结构：在第一箭确定后，剩余未被覆盖气球构成独立子问题，其最优解与原问题最优解的剩余部分一致。【底层数据结构与实现细节】 • 排序稳定性无关紧要，但必须按 end 升序；若 end 相同，start 顺序不影响结果（因右端点相同，取任一右端点均可覆盖全部相同 end 的气球）。 • 时间复杂度：O(n log n) 主导于排序；空间复杂度：O(1)（原地排序时，忽略输入存储）。 • 边界鲁棒性：需处理空数组、单气球、重叠全包含（如[1,5],[2,3]）、无重叠（如[1,2],[3,4]）等case。 • 对比动态规划：本题不可直接DP，因状态定义困难（“覆盖前i个气球的最少箭数”无法仅由i-1推得，缺少无后效性：是否覆盖第i个气球取决于箭位，而箭位又影响后续）；贪心恰利用了区间的几何可序性，绕过了状态爆炸。【扩展关联知识点】 • 本题是经典“区间调度”问题变种，与“最多不重叠区间数”（LC435）互为对偶：后者求最大兼容子集，贪心选 end 最小者并移除与其冲突的所有；本题求最小覆盖箭数，等价于将区间划分为最少的相交组（每组可被一箭覆盖），而每组的极小代表即该组所有区间右端点的最小值。 • 进阶变形：若箭有射程限制（如只能射长度L的连续区间），则退化为滑动窗口+贪心，需结合双指针；若气球可旋转/非区间模型，则需计算几何支持。 • 工程实践注意：浮点坐标需考虑精度误差，建议用整数或自定义比较器避免 == 判断；大规模数据下可考虑基数排序优化至 O(n)（当坐标范围有限时）。 - 代码示例（C++，标准库实现，含注释）： ``` #include #include using namespace std; int findMinArrowShots(vector>& points) { if (points.empty()) return 0; // 按右端点升序排序；若右端点相同，按左端点降序（非必须，但利于理解：左越大的越难被覆盖，优先处理） sort(points.begin(), points.end(), [](const vector& a, const vector& b) { if (a[1] != b[1]) return a[1] < b[1]; return a[0] > b[0]; }); int arrows = 1; int arrow_pos = points[0][1]; // 第一箭射在第一个气球的右端点 for (int i = 1; i < points.size(); ++i) { // 若当前气球左端点大于上一箭位置，说明未被覆盖，需新箭 if (points[i][0] > arrow_pos) { arrows++; arrow_pos = points[i][1]; // 新箭射在当前气球右端点 } // 否则当前气球被 arrow_pos 覆盖（因 points[i][0] <= arrow_pos <= points[i][1] 自动满足） } return arrows; } ``` - 补充Python版本（更简洁，体现lambda与内置函数）： ``` def findMinArrowShots(points): if not points: return 0 points.sort(key=lambda x: x[1]) # 仅按end排序即可 arrows = 1 arrow_pos = points[0][1] for i in range(1, len(points)): if points[i][0] > arrow_pos: arrows += 1 arrow_pos = points[i][1] return arrows ```

小鹏自动驾驶感知实习一面

全站热榜

创作者周榜