LeetCode 452中等贪心
用最少数量的箭引爆气球 图解题解
这道题到底在问什么
有一些气球贴在墙上，points[i] = [xstart, xend] 表示气球水平直径的开始和结束坐标。若一支箭在坐标 x 处射出，且 xstart <= x <= xend，这个气球会被引爆。请返回引爆所有气球所必须射出的最小弓箭数。
- 输入
- points = [[10,16],[2,8],[1,6],[7,12]]
- 输出
- 2
- 解释
- x=6 可引爆 [1,6] 和 [2,8]；x=12 可引爆 [7,12] 和 [10,16]。
- 输入
- points = [[1,2],[2,3],[3,4],[4,5]]
- 输出
- 2
最优解：一步一步想明白
- 3区间贪心通常先问：当前必须处理的区间，最晚能把选择拖到哪里。
- 4把箭放在当前最早右端点，不会错过当前气球，同时给后续气球留下最大的重叠机会。
- 5points.sort(key=lambda p: p[1])原输入顺序是乱的。按右端点排序后，最早结束的气球会先被处理。
- 6arrows = 1; end = points[0][1]第一支箭必须引爆第一个气球。射在 x=6 是最靠右的位置，给后面的区间留下最多机会。
- 7start <= end[2,8] 包含 x=6，同一支箭可以顺便引爆它。注意这里不更新 end，因为箭的位置已经固定在 6。
- 8if start > end:当前气球左端点 7 已经在箭 6 的右边，必须增加一支箭。
- 9arrows += 1; end = finish新箭同样射在当前气球的右端点 12，让它尽量还能覆盖后面的气球。
- 10start <= end[10,16] 包含 x=12，所以第二支箭也能引爆它。
- 11for 循环结束每个气球都被某支箭覆盖，最终答案是 2。
- 12return arrowsarrows 记录的就是必须新增箭的次数，也就是最少箭数。
- 13题目是闭区间，箭射在端点也算击中。
- 16这和活动选择、无重叠区间是同一类贪心骨架。
⚠️ 容易写错的地方
✗ 错：按左端点排序后贪心
✓ 对：按右端点排序
右端点越早越紧迫，先固定它最安全。
✗ 错：start == end 时新增箭
✓ 对：只有 start > end 才新增箭
端点相交时同一支箭可以射中两个气球。
✗ 错：覆盖新区间时更新 end
✓ 对：覆盖时不更新 end
箭的位置已经固定，不能因为新区间更长就移动箭。
完整代码（Python）
Python
class Solution:
def findMinArrowShots(self, points):
points.sort(key=lambda p: p[1])
arrows = 1
end = points[0][1]
for start, finish in points[1:]:
if start > end:
arrows += 1
end = finish
return arrows复杂度
时间复杂度
O(n log n)
主要开销来自按右端点排序。
空间复杂度
O(1)
除排序实现内部开销外，只保存 arrows 和 end。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 用最少数量的箭引爆气球 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「贪心」，换最直接的暴力解会差在哪？+
贪心抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。