452. 用最少数量的箭引爆气球（力扣LeetCode）

文章目录

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

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

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

示例 1：

示例 2：

示例 3：

提示:

• 1 <= points.length <= 10
• points[i].length == 2
• -2 <= xstart < xend <= 2 - 1

贪心算法

如何使用最少的弓箭呢？

直觉上来看，貌似只射重叠最多的气球，用的弓箭一定最少，那么有没有当前重叠了三个气球，我射两个，留下一个和后面的一起射这样弓箭用的更少的情况呢？

尝试一下举反例，发现没有这种情况。

那么就试一试贪心吧！局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。

算法确定下来了，那么如何模拟气球射爆的过程呢？是在数组中移除元素还是做标记呢？

如果真实的模拟射气球的过程，应该射一个，气球数组就remove一个元素，这样最直观，毕竟气球被射了。

但仔细思考一下就发现：如果把气球排序之后，从前到后遍历气球，被射过的气球仅仅跳过就行了，没有必要让气球数组remove气球，只要记录一下箭的数量就可以了。

以上为思考过程，已经确定下来使用贪心了，那么开始解题。

为了让气球尽可能的重叠，需要对数组进行排序。

那么按照气球起始位置排序，还是按照气球终止位置排序呢？

其实都可以！只不过对应的遍历顺序不同，我就按照气球的起始位置排序了。

既然按照起始位置排序，那么就从前向后遍历气球数组，靠左尽可能让气球重复。

从前向后遍历遇到重叠的气球了怎么办？

如果气球重叠了，重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。

以题目示例： [[10,16],[2,8],[1,6],[7,12]]为例，如图：（方便起见，已经排序）

可以看出首先第一组重叠气球，一定是需要一个箭，气球3，的左边界大于了 第一组重叠气球的最小右边界，所以再需要一支箭来射气球3了。

代码

这段代码是解决上述问题的C++实现，即用最少数量的箭引爆所有气球。以下是对代码的详细注释：

class Solution {
public:
    // 自定义比较函数
    // 对于两个气球 a 和 b，按照其开始坐标进行升序排序
    static bool cmp(vector<int> a,vector<int> b)
    {
        return a[0] < b[0];
    }
    
    // 主要的函数，用于找到引爆所有气球所需要的最少箭数
    int findMinArrowShots(vector<vector<int>>& points) {
        // 如果没有气球，就不需要射箭
        if(points.empty()) return 0;
        
        // 初始化答案为1，因为至少需要一支箭
        int ans = 1;
        
        // 对所有的气球按照开始坐标进行排序
        sort(points.begin(), points.end(), cmp);
        
        // 遍历所有气球的开始和结束坐标
        for(int i = 1; i < points.size(); i++) {
            // 如果当前气球的开始坐标大于前一个气球的结束坐标
            if(points[i][0] > points[i - 1][1]) {
                // 说明不能用同一支箭引爆这两个气球
                // 需要一支新的箭，因此答案加1
                ans++;
            } else {
                // 如果当前气球的开始坐标小于或等于前一个气球的结束坐标
                // 更新当前气球的结束坐标为两个气球结束坐标的较小值
                // 这样做是为了缩小接下来气球的有效射击区间
                // 使得这支箭尽可能多地引爆后面的气球
                points[i][1] = min(points[i - 1][1], points[i][1]);
            }
        }
        
        // 返回最终计算的答案
        return ans;
    }
};

代码的工作流程如下：

1. 自定义排序函数： cmp函数用于比较两个气球的开始坐标，确保在排序时气球能够按照开始坐标从小到大排列。

2. findMinArrowShots 函数：

   • 首先检查points数组是否为空，为空则返回0，因为没有气球需要射击。
   • 初始化箭的数量ans为1，因为至少需要一支箭开始射击。
   • 使用std::sort函数，根据自定义的比较函数cmp对气球数组points进行排序。
   • 遍历排序后的气球数组，从第二个气球（索引1）开始。
   • 对于每个气球，检查其开始坐标是否大于前一个气球的结束坐标。如果是，意味着这两个气球不能被同一支箭引爆，因此增加箭的数量ans。
   • 如果当前气球的开始坐标不大于前一个气球的结束坐标，这两个气球的交叉区域就是它们都能被引爆的区域。为了保留这个区域，同时考虑后续的气球，将当前气球的结束坐标更新为其与前一个气球结束坐标的较小值。
   • 最后，返回箭的总数量ans。

通过上述方法，代码高效地计算出了引爆所有气球所需的最小箭数。