LC452
用最少数量的箭引爆气球
区间 · 射气球可视化:区间时间轴points=[[10,16],[2,8],[1,6],[7,12]] 最少箭。
时间 O(n)空间 O(1)
题目1 / 10
题目与输入建立输入、目标与算法心智
在数轴上射箭,一支箭若穿过 x 则引爆该气球
正在加载算法场景...
当前发生了什么
points=[[10,16],[2,8],[1,6],[7,12]] 最少箭。
机器状态
箭位置、排序、i。
为什么正确
按 end 排序,箭射当前 end,跳过被覆盖,下一未被盖需新箭。
不变量
与无重叠区间对偶:箭=点,气球=区间。
面试怎么说
end 排序贪心 O(n log n)。
人类输入
points=[[10,16],[2,8],[1,6],[7,12]] 最少箭。
机制
按 end 排序,箭射当前 end,跳过被覆盖,下一未被盖需新箭。
机器状态
箭位置、排序、i。
可观察结果
最少 2 箭。
不变量
- · 与无重叠区间对偶:箭=点,气球=区间。
常见误区
- · sort by end 同 435。
迁移练习
- · LC435 无重叠
- · LC56 合并
面试怎么答
end 排序贪心 O(n log n)。