Medium

题目描述

有一些球形的气球贴在一面用 XY 平面表示的墙上。这些气球表示为一个二维整数数组 points，其中 points[i] = [xstart, xend] 表示一个在水平方向上从 xstart 到 xend 伸展的气球。你不知道气球的确切 y 坐标。

箭可以沿着 x 轴从不同点直接垂直（沿正 y 方向）射出。在 xstart 和 xend 之间的气球可以通过在 x 处射出的箭引爆，当且仅当 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 <= points.length <= 10^5
  • points[i].length == 2
  • -2^31 <= xstart < xend <= 2^31 - 1

解题思路

这是一个典型的贪心算法问题，类似于区间调度问题。

核心思路：

  1. 为了用最少的箭引爆所有气球，我们需要尽可能让一支箭能够引爆更多的气球
  2. 如果多个气球有重叠区域，那么在重叠区域射出一支箭就能同时引爆这些气球
  3. 关键是找到最优的射箭位置

算法步骤：

  1. 排序：按照气球的结束位置（右端点）进行排序。这样可以保证贪心选择的最优性
  2. 贪心选择：从左到右遍历排序后的气球，尽可能选择能引爆当前气球的最右边位置射箭
  3. 更新状态：每次射箭后，跳过所有被当前箭引爆的气球

为什么按右端点排序？ 按右端点排序后，我们总是在当前气球的最右端射箭。这样能保证：

  • 当前气球一定被引爆
  • 如果有其他气球与当前气球重叠，在右端点射箭能引爆尽可能多的气球
  • 对于后续气球，这是最优的贪心选择

时间复杂度主要来自排序操作，空间复杂度为常数级别。

代码实现

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.empty()) return 0;
        
        // 按右端点排序
        sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });
        
        int arrows = 1;
        int arrowPos = points[0][1]; // 第一支箭射在第一个气球的右端点
        
        for (int i = 1; i < points.size(); i++) {
            // 如果当前气球的左端点大于箭的位置，需要新的箭
            if (points[i][0] > arrowPos) {
                arrows++;
                arrowPos = points[i][1]; // 新箭射在当前气球的右端点
            }
        }
        
        return arrows;
    }
};

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if not points:
            return 0
        
        # 按右端点排序
        points.sort(key=lambda x: x[1])
        
        arrows = 1
        arrow_pos = points[0][1]  # 第一支箭射在第一个气球的右端点
        
        for i in range(1, len(points)):
            # 如果当前气球的左端点大于箭的位置，需要新的箭
            if points[i][0] > arrow_pos:
                arrows += 1
                arrow_pos = points[i][1]  # 新箭射在当前气球的右端点
        
        return arrows

public class Solution {
    public int FindMinArrowShots(int[][] points) {
        if (points.Length == 0) return 0;
        
        // 按右端点排序
        Array.Sort(points, (a, b) => a[1].CompareTo(b[1]));
        
        int arrows = 1;
        int arrowPos = points[0][1]; // 第一支箭射在第一个气球的右端点
        
        for (int i = 1; i < points.Length; i++) {
            // 如果当前气球的左端点大于箭的位置，需要新的箭
            if (points[i][0] > arrowPos) {
                arrows++;
                arrowPos = points[i][1]; // 新箭射在当前气球的右端点
            }
        }
        
        return arrows;
    }
}

var findMinArrowShots = function(points) {
    points.sort((a, b) => a[1] - b[1]);
    
    let arrows = 1;
    let end = points[0][1];
    
    for (let i = 1; i < points.length; i++) {
        if (points[i][0] > end) {
            arrows++;
            end = points[i][1];
        }
    }
    
    return arrows;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要来自排序操作，其中 n 是气球的数量
空间复杂度O(1)只使用了常数额外空间，排序为原地排序

相关题目