用最少数量的箭引爆气球(LeetCode 452)
哪些公司问过
答案要点
- 将气球按右端点升序排序
- 贪心:箭射在当前最早结束气球的右端点
- 下一气球左端点大于当前箭位置时才新增一支箭并更新位置
- 时间复杂度O(n log n),瓶颈在排序
- 端点相接也能射爆,判断需用严格大于
易错点
- 端点相接时误判为需要新箭,应使用严格大于
- 比较器用两数相减导致整数溢出
- 按左端点排序却不维护最小右端点,结果偏少或偏多
面试官常见追问
- 为什么按右端点贪心是对的?
- 能按左端点排序吗?
- 和435无重叠区间有什么联系?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。