452. 用最少数量的箭引爆气球[排序+贪心]

本文主要是介绍452. 用最少数量的箭引爆气球[排序+贪心]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/?envType=study-plan-v2&envId=top-interview-150

题目描述

有一些球形气球贴在一堵用 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-1 所示，我们随机射出一支箭，引爆了除红色气球以外的所有气球。我们称所有引爆的气球为「原本引爆的气球」，其余的气球为「原本完好的气球」。可以发现，如果我们将这支箭的射出位置稍微往右移动一点，那么我们就有机会引爆红色气球，如图 1-2 所示。

那么我们最远可以将这支箭往右移动多远呢？将这支箭的射出位置移动到这个右边界位置，这也是最远可以往右移动到的位置：如图 1-3 所示，只要我们再往右移动一点点，这个气球就无法被引爆了。

因此，我们可以断定：

一定存在一种最优（射出的箭数最小）的方法，使得每一支箭的射出位置都恰好对应着某一个气球的右边界。

这是为什么？我们考虑任意一种最优的方法，对于其中的任意一支箭，我们都通过上面描述的方法，将这支箭的位置移动到它对应的「原本引爆的气球中最靠左的右边界位置」，那么这些原本引爆的气球仍然被引爆。右侧也已经到达了这支箭的极限。

又因为右侧边界排序过后，是有序的，我们可以每次取当前右侧边界最小的气球，把这个气球的右边界作为发射箭的位置，只要所有的左边界比我这个位置小的都可以打中（因为右边界从小到大呀！），所以直到打不中的时候，更新射箭的位置为当前的最小右边界的位置，继续扫描判断。
注意：

在排序的自定义比较器中，不能直接返回i[1]-i[2];因为会有越界问题，使用if-else判断解决；

代码

class Solution {public int findMinArrowShots(int[][] points) {if(points.length == 0){return 0;}Arrays.sort(points, new Comparator<int[]>(){public int compare(int[] point1, int[] point2){// return point1[1] - point2[1];   // 注意这里不能这样写，会溢出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[] point: points){if(point[0] >  pos){   //  如果你的左边界比我的射位置靠右，射不到了，要更新射箭位置为当前最小的右边界，pos = point[1];ans += 1;}}return ans;}
}