LeetCode日记–452. Minimum Number of Arrows to Burst Balloons

发布于 2020-11-23  133 次阅读


题目如下:

There are some spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it's horizontal, y-coordinates don't matter, and hence the x-coordinates of start and end of the diameter suffice. The start is always smaller than the end.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps traveling up infinitely.

Given an array points where points[i] = [xstart, xend], return the minimum number of arrows that must be shot to burst all balloons.

Example 1:

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).

Example 2:

Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4

Example 3:

Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2

Example 4:

Input: points = [[1,2]]
Output: 1

Example 5:

Input: points = [[2,3],[2,3]]
Output: 1

Constraints:

0 <= points.length <= 104
points[i].length == 2
-231 <= xstart < xend <= 231 - 1

题目给了一个二维数组,其中里面的每个一维数组是一个区间,代表每个气球的宽度和所在的范围。

思路:

方法一(贪心算法):

我自己的思路是使用贪心算法:

1.找出一个点,在该点射出箭是当前情况下能够引爆最多气球数的最优解(需要遍历所有气球,若该点在遍历到的气球区间内则引爆数+1)

2.删除被引爆的点,继续重复step1,直到所有气球被引爆。

但是这个方法需要n^2时间复杂度,而且空间上需要每次遍历记下能引爆的气球的集合...时间复杂度和空间复杂度都过高了,这里不再考虑。

方法二(贪心算法+排序):

图源为官方题解

观察上图我们可以知道,若想一次性引爆尽可能多的气球,我们需要关注的就是每个气球范围的右边界。那么根据木桶原理,我们就要在当前这一组气球中右边界最小处射出箭。

同时,若气球的左边界大于了当前的射入点,我们可以认为他不属于本组气球,我们无法在本组将其引爆。

因此我们先按照气球的右边界大小进行升序排序,然后再使用贪心算法进行分别引爆。

方法二代码:

class Solution {
    public int findMinArrowShots(int[][] points) {
        if(points.length==0){
            return 0;
        }
        Arrays.sort(points,new Comparator<int[]>(){
            public int compare(int[] a1,int[]a2){
                if(a1[1]>a2[1]){
                    return 1;
                }
                else{
                    return -1;
                }
            }
        });
        // 因为前面的case处理,说明至少需要一只箭
        int res=1;
        int minRightBorder = points[0][1];
        for(int[] a:points){
            // 对于每个气球,若箭的射入点小于其左边界,则说明无法引爆气球,则箭数++,更新射入点
            if(a[0]>minRightBorder){
                ++res;
                minRightBorder = a[1];
            }
        }
        return res;
    }
}

你好哇!欢迎来到雷公马碎碎念的地方:)