友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
452. 用最少数量的箭引爆气球
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中 points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend 之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend，且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数。
示例 1：
输入：points = [[10,16],[2,8],[1,6],[7,12]] 输出：2 解释：气球可以用2支箭来爆破: -在x = 6处射出箭，击破气球[2,8]和[1,6]。 -在x = 11处发射箭，击破气球[10,16]和[7,12]。
示例 2：
输入：points = [[1,2],[3,4],[5,6],[7,8]] 输出：4 解释：每个气球需要射出一支箭，总共需要4支箭。
示例 3：
输入：points = [[1,2],[2,3],[3,4],[4,5]] 输出：2 解释：气球可以用2支箭来爆破: - 在x = 2处发射箭，击破气球[1,2]和[2,3]。 - 在x = 4处射出箭，击破气球[3,4]和[4,5]。
提示:
-
1 <= points.length <= 105 -
points[i].length == 2 -
-2^31^ <= x~start~ < x~end~ <= 2^31^ - 1
思路分析
对坐标区间排序，然后进行区间合并，最后统计只剩几个区间即可。看题解，也不需要保存区间，只需要记录最后一个区间的右端就可以统计出区间数量。
看题解，说这是一道贪心算法的题。
-
如果按照我上面合并区间的做法，那么就是一道 Merge Intervals 区间合并 的题目。
-
如果按照贪心的思路来解题，首先排序时，需要根据右端位置排序。每次记录最右端的位置，拿当前区间的左端，跟目前最右端的位置进行比较，只有在没有交集时，才增大射箭数量。
| 看“代码随想录”的解释，D瓜哥的区间解法是贪心思路。 |
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-06-19 21:20:51
*/
public int findMinArrowShots(int[][] points) {
Arrays.sort(points, Comparator.comparingInt(a -> a[0]));
List<int[]> inter = new ArrayList<>();
inter.add(points[0]);
for (int i = 1; i < points.length; i++) {
int[] point = points[i];
int[] last = inter.getLast();
if (last[1] < point[0]) {
// 新区间在已处理区间的后面，则直接新增
inter.add(point);
} else {
// 有重叠，则进行区间合并
last[0] = Math.max(last[0], point[0]);
last[1] = Math.min(last[1], point[1]);
}
}
return inter.size();
}