Leetcode 452. 用最少数量的箭引爆气球

2023-12-22 17:25:15

题意理解

? ? ? ? 气球用一个闭区间表示,击中区间内任意一个位置,气球会被引爆。

? ? ? ? 区间指示了气球的位置和气球的可射击范围。

? ? ? ? 若两个气球位置有重叠,则一只箭能解决引爆两个气球。

? ? ? ? 目标:尽可能射击气球重叠最多的位置,用最少的箭引爆所有气球。

解题思路

? ? ? ? 采用贪心思想来解题,全局最优是用最少的箭引爆最多的气球,

? ? ? ? 则局部最优:尽可能射击气球重叠最多的地方

? ? ? ? 为了实现局部最优,我们需要对气球的重叠部分进行判断,为了简单进行判断,我们以左区间为标准从小到大进行排序。

? ? ? ? 当第i个区间的左边界<=第i-1个区间的右边界时,——两个气球重叠。一只箭可以引爆两个气球。 为了尽可能爆掉最多的气球,尽可能从重叠边缘的最右边射击,以确保爆掉最多的气球。

? ? ? ? 所以第i+1个区间的左边界需要和重叠区域的最右边界比较,若重叠,则进行下一个气球的判断,否则,增加一只箭。

????????当第i个区间的左边界>第i-1个区间的右边界时,——两个气球不重叠。需要增加一只箭引爆第i个气球?

1.贪心解题

注意:这里的输入限制如下所示,可能造成溢出,所以推荐使用Integer.comparen比较方法可以防止这个问题。

? ? ? ? 在日常解题过程中也推荐有限选择有现有类内置的一些方法。

public int findMinArrowShots(int[][] points) {
        if(points.length==0) return 0;
        //记录箭数
        int count=1;
        //对point左边界升序排序
        // 使用Integer内置比较方法,不会溢出
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
        //与左边的气球比较
        for(int i=1;i<points.length;i++){
            if(points[i][0]<=points[i-1][1]){//有重叠
                points[i][1]=Math.min(points[i][1],points[i-1][1]);
            }else{
                count++;//不重叠,增加一只箭
            }
        }
        return count;
    }

2.分析

时间复杂度:O(nlogn) 遍历气球的时间O(n)+排序的时间O(nlogn)

空间复杂度:O(logn) 排序所需的栈空间

n为输入数组大小

文章来源:https://blog.csdn.net/lt_BeiMo/article/details/135149163
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。