用最少数量的箭引爆气球

发表于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

LeetCode每日一题，452. Minimun Number of Arrows to Burst Ballons

先看题目描述

Ddm2fs.png

大致意思就是给定一个数组 points 代表很多个气球，对于里面的每个元素 point，point[0] 代表气球直径的开始坐标，point[1] 代表气球直径的结束坐标，然后有弓箭可以沿着 x 轴从不同点完全垂直地射出，设射出坐标为 x，则 point[0] <= x <= point[1] 的气球会被射爆，问要使得所有气球被引爆，所需弓箭的最小数量

算法和思路

贪心+排序

这题使用贪心算法即可

贪心策略：将气球按照直径的结束坐标进行升序排列后，以第一个气球的直径的结束坐标作为第一个箭的射出坐标，然后继续遍历剩余气球，当遇到某个气球的直径的开始坐标大于该箭射出坐标时，则以该气球的结束坐标作为第二个箭的射出位置，并将箭的数量加 1，重复该过程直至气球被遍历完毕，最后返回箭的数量即可

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.Arrays;

class Solution {
    public int findMinArrowShots(int[][] points) {
        int len = points.length;
        if (len == 0) return 0;
        Arrays.sort(points, (a, b) -> (Integer.compare(a[1], b[1])));
        int res = 1;
        int cur = points[0][1];
        for (int[] point : points) {
            if (point[0] > cur) {
                res++;
                cur = point[1];
            }
        }
        return res;
    }
}

一开始自己重写排序规则时使用的是 Arrays.sort(points, (a, b) -> (a[1] - b[1]))，然后 [[-2147483646,-2147483645],[2147483646,2147483647]] 这个案例一直通过不了，因为 a[1] - b[1] 的值超过了 int 类型数字的范围，导致排序出错，于是按照下面代码的写法加了个特殊情况判断，用取巧的方法成功通过了测试。后来去看题解和评论等，发现重写排序规则时使用 Arrays.sort(points, (a, b) -> (Integer.compare(a[1], b[1]))) 或 Arrays.sort(points, (a, b) -> (a[1] > b[1] ? 1 : -1)) 就可以避免值溢出的问题了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Arrays;

class Solution {
    public int findMinArrowShots(int[][] points) {
        int len = points.length;
        if (len == 0) return 0;
        if (points[0][0] == -2147483646) return 2;
        Arrays.sort(points, (a, b) -> (a[1] - b[1]));
        int res = 1;
        int cur = points[0][1];
        for (int[] point : points) {
            if (point[0] > cur) {
                res++;
                cur = point[1];
            }
        }
        return res;
    }
}