0452. 用最少数量的箭引爆气球 #
- 标签:贪心、数组、排序
- 难度:中等
题目大意 #
描述:在一个坐标系中有许多球形的气球。对于每个气球,给定气球在 x 轴上的开始坐标和结束坐标 $(x_{start}, x_{end})$。
同时,在 $x$ 轴的任意位置都能垂直发出弓箭,假设弓箭发出的坐标就是 x。那么如果有气球满足 $x_{start} \le x \le x_{end}$,则该气球就会被引爆,且弓箭可以无限前进,可以将满足上述要求的气球全部引爆。
现在给定一个数组 points
,其中 $points[i] = [x_{start}, x_{end}]$ 代表每个气球的开始坐标和结束坐标。
要求:返回能引爆所有气球的最小弓箭数。
说明:
- $1 \le points.length \le 10^5$。
- $points[i].length == 2$。
- $-2^{31} \le x_{start} < x_{end} \le 2^{31} - 1$。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:贪心算法 #
弓箭的起始位置和结束位置可以看做是一段区间,直观上来看,为了使用最少的弓箭数,可以尽量射中区间重叠最多的地方。
所以问题变为了:如何寻找区间重叠最多的地方,也就是区间交集最多的地方。
我们将 points
按结束坐标升序排序(为什么按照结束坐标排序后边说)。
然后维护两个变量:一个是当前弓箭的坐标 arrow_pos
、另一个是弓箭的数目 count
。
为了尽可能的穿过更多的区间,所以每一支弓箭都应该尽可能的从区间的结束位置穿过,这样才能覆盖更多的区间。
初始情况下,第一支弓箭的坐标为第一个区间的结束位置,然后弓箭数为 $1$。然后依次遍历每段区间。
如果遇到弓箭坐标小于区间起始位置的情况,说明该弓箭不能引爆该区间对应的气球,需要用新的弓箭来射,所以弓箭数加 $1$,弓箭坐标也需要更新为新区间的结束位置。
最终返回弓箭数目。
再来看为什么将 points
按结束坐标升序排序而不是按照开始坐标升序排序?
其实也可以,但是按开始坐标排序不如按结束坐标排序简单。
按开始坐标升序排序需要考虑一种情况:有交集关系的区间中,有的区间结束位置比较早。比如 [0, 6]、[1, 2] [4, 5]
,按照开始坐标升序排序的话,就像下图一样:
|
|
第一箭的位置需要进行迭代判断,取区间 [0, 6]、[1, 2]
中结束位置最小的位置,即 arrow_pos = min(points[i][1], arrow_pos)
,然后再判断接下来的区间是否能够引爆。
而按照结束坐标排序的话,箭的位置一开始就确定了,不需要再改变和判断箭的位置,直接判断区间即可。
思路 1:代码 #
- 按照结束位置升序排序
|
|
- 按照开始位置升序排序
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n \times \log n)$, 其中 $n$ 是数组
points
的长度。 - 空间复杂度:$O(\log n)$。