用最少数量的箭引爆气球（Java）

ゝ一纸荒年。 2024-04-06 14:03 58阅读 0赞

### 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 < = p o i n t s . l e n g t h < = 1 0 5 1 <= points.length <= 10^5 1<=points.length<=105  
 p o i n t s \[ i \] . l e n g t h = = 2 points\[i\].length == 2 points\[i\].length==2  
 − 2 31 < = x s t a r t < x e n d < = 2 31 − 1 -2^\{31\} <= xstart < xend <= 2^\{31\} - 1 −231<=xstart<xend<=231−1

#### 思路： ####

##### 排序 + 贪心： #####

这道题的关键就是（实际上所有贪心的关键）就是寻找子问题的最优解  
这里的最优解就是最左右边界

1.  将所有区间按最右侧边界大小升序排序
2.  取出右边界最小的区间，该右边界即为箭射出的地方
3.  遍历数组，如果取出区间的左边界小于箭射出的位置，则该气球会被这个箭引爆
4.  如果左边界不小于箭射出的位置，则需要另一只箭，这只箭射出的位置就是该区间的右边界；重复以上步骤，依次遍历所有区间

##### 代码（Java）： #####

import java.util.Arrays;
    import java.util.Comparator;
    
    public class min_arrow {
        
    
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		int[][] points = {
        {
        10,16},{
        2,8},{
        1,6},{
        7,12}};
    		System.out.println(findMinArrowShots(points));
    	}
    	public static int findMinArrowShots(int[][] points) {
        
    		if(points.length == 0)
    			return 0;
    		Arrays.sort(points, new Comparator<int[]>() {
        
    			public int compare(int[] point1, int[] point2) {
        
    				if(point1[1] > point2[1]) {
        
    					return 1;
    				}else if(point1[1] < point2[1]) {
        
    					return -1;
    				}else {
        
    					return 0;
    				}
    			}
    		});
    		int pos = points[0][1];
    		int ans = 1;
    		for(int[] balloon: points) {
        
    			if(balloon[0] > pos) {
        
    				pos = balloon[1];
    				ans++;
    			}
    		}
    		return ans;
        }
    }

##### 复杂度分析： #####

*  时间复杂度：O(nlogn)，其中 n 是数组points 的长度。排序的时间复杂度为 O(nlogn)，对所有气球进行遍历并计算答案的时间复杂度为 O(n)，其在渐进意义下小于前者，因此可以忽略。
 *  空间复杂度：O(logn)，即为排序需要使用的栈空间。

来源：[力扣（LeetCode）][LeetCode]

仅供学习参考。

[LeetCode]: https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons