0452. 用最少数量的箭引爆气球

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:
1
2
3
4
5
输入points = [[10,16],[2,8],[1,6],[7,12]]
输出2
解释气球可以用 2 支箭来爆破:
- 在x = 6 处射出箭击破气球 [2,8] 和 [1,6]
- 在x = 11 处发射箭击破气球 [10,16] 和 [7,12]
  • 示例 2:
1
2
3
输入points = [[1,2],[3,4],[5,6],[7,8]]
输出4
解释每个气球需要射出一支箭总共需要 4 支箭

解题思路 #

思路 1:贪心算法 #

弓箭的起始位置和结束位置可以看做是一段区间,直观上来看,为了使用最少的弓箭数,可以尽量射中区间重叠最多的地方。

所以问题变为了:如何寻找区间重叠最多的地方,也就是区间交集最多的地方。

我们将 points 按结束坐标升序排序(为什么按照结束坐标排序后边说)。

然后维护两个变量:一个是当前弓箭的坐标 arrow_pos、另一个是弓箭的数目 count

为了尽可能的穿过更多的区间,所以每一支弓箭都应该尽可能的从区间的结束位置穿过,这样才能覆盖更多的区间。

初始情况下,第一支弓箭的坐标为第一个区间的结束位置,然后弓箭数为 $1$。然后依次遍历每段区间。

如果遇到弓箭坐标小于区间起始位置的情况,说明该弓箭不能引爆该区间对应的气球,需要用新的弓箭来射,所以弓箭数加 $1$,弓箭坐标也需要更新为新区间的结束位置。

最终返回弓箭数目。

再来看为什么将 points 按结束坐标升序排序而不是按照开始坐标升序排序?

其实也可以,但是按开始坐标排序不如按结束坐标排序简单。

按开始坐标升序排序需要考虑一种情况:有交集关系的区间中,有的区间结束位置比较早。比如 [0, 6]、[1, 2] [4, 5],按照开始坐标升序排序的话,就像下图一样:

1
2
3
[0..................6]
   [1..2]    
             [4..5]

第一箭的位置需要进行迭代判断,取区间 [0, 6]、[1, 2] 中结束位置最小的位置,即 arrow_pos = min(points[i][1], arrow_pos),然后再判断接下来的区间是否能够引爆。

而按照结束坐标排序的话,箭的位置一开始就确定了,不需要再改变和判断箭的位置,直接判断区间即可。

思路 1:代码 #

  1. 按照结束位置升序排序
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if not points:
            return 0
        points.sort(key=lambda x: x[1])
        arrow_pos = points[0][1]
        count = 1
        for i in range(1, len(points)):
            if arrow_pos < points[i][0]:
                count += 1
                arrow_pos = points[i][1]
        return count
  1. 按照开始位置升序排序
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if not points:
            return 0
        points.sort(key=lambda x: x[0])
        arrow_pos = points[0][1]
        count = 1
        for i in range(1, len(points)):
            if arrow_pos < points[i][0]:
                count += 1
                arrow_pos = points[i][1]
            else:
                arrow_pos = min(points[i][1], arrow_pos)
        return count

思路 1:复杂度分析 #

  • 时间复杂度:$O(n \times \log n)$, 其中 $n$ 是数组 points 的长度。
  • 空间复杂度:$O(\log n)$。
本站总访问量  次  |  您是本站第  位访问者