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

约 5 分钟
文章信息 12 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 LeetCode 75 面试经典 150 题 字节 美团 百度 快手 虾皮
标签
数组 排序 贪心

题目描述

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

image-20260928221041170

image-20260928221041171

题意分析

每个气球对应一个水平闭区间，选择一个横坐标射箭，就能同时引爆所有包含该坐标的气球。求覆盖全部气球所需的最少箭数，不需要返回具体射箭位置。

命中区间端点也有效，因此只在一个端点相接的两个气球可以共用一箭。多个区间逐个相交并不一定有共同交点，必须存在同一个坐标落在所有区间内，才可以共用一箭。

解法：按右端点排序贪心

核心思路

[!blue]

按右端点从小到大排序，先考虑结束最早的未覆盖区间，它无论如何都必须被某支箭命中。把这支箭放在它的右端点，既能命中它，也能尽可能靠右地兼顾后续区间。

这个选择可以用交换来证明：假设某个最优方案用位置 x 命中当前最早结束的区间，必有 x <= end。把它右移到 end 后仍命中当前区间；其他被原箭命中的剩余区间，左端点不大于 x，右端点又都不小于 end，因此移动后仍然命中。箭数无需增加，总能把一个最优方案改成当前贪心选择。

用 arrowPos 保存最近放下的箭位。按右端点排序后，当前区间的右端点必然不小于 arrowPos，所以只需检查左端点：若 start <= arrowPos，这支箭已覆盖当前气球；若 start > arrowPos，此前所有箭都更靠左，必须新增一箭，再放到当前右端点。

已被覆盖时，原箭位要保持不变，因为它还负责覆盖此前的一组气球，不能随新区间的右端点继续右移。每当确实需要新箭时，再对剩余未覆盖区间应用同一选择，最终得到最少箭数。

解题步骤

  1. 空输入返回零；其余情况按右端点升序排序，Java 使用安全的整数比较函数。
  2. 将第一支箭放在第一个区间的右端点，初始化箭数为一。
  3. 顺序扫描剩余区间，若左端点不大于当前箭位，保持已有状态。
  4. 只有左端点严格大于箭位时，才增加箭数并把新箭放在当前右端点。
  5. 返回累计箭数。

代码实现

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) {
            return 0;
        }

        Arrays.sort(points, (first, second) -> Integer.compare(first[1], second[1]));
        int arrows = 1;
        int arrowPos = points[0][1];

        for (int idx = 1; idx < points.length; idx++) {
            // 闭区间中 start <= arrowPos 仍然能被当前箭引爆。
            if (points[idx][0] > arrowPos) {
                arrows++;
                arrowPos = points[idx][1];
            }
        }

        return arrows;
    }
}

import "sort"

func findMinArrowShots(points [][]int) int {
    if len(points) == 0 {
        return 0
    }

    sort.Slice(points, func(i int, j int) bool {
        return points[i][1] < points[j][1]
    })
    arrows := 1
    arrowPos := points[0][1]
    for idx := 1; idx < len(points); idx++ {
        // 闭区间中 start <= arrowPos 仍然能被当前箭引爆。
        if points[idx][0] > arrowPos {
            arrows++
            arrowPos = points[idx][1]
        }
    }
    return arrows
}

复杂度分析

  • 时间复杂度：$O(n \log n)$，排序占主导，扫描为 $O(n)$。
  • 空间复杂度：贪心扫描为 $O(1)$；计入库排序，Java 最坏为 $O(n)$，Go 为 $O(\log n)$ 调用栈。

关键点总结

[!green]

  • 按右端点排序，才能为第一个未覆盖区间立即确定最靠右的安全箭位。
  • 闭区间端点也算命中，因此只有 start > arrowPos 才需要新箭。
  • 已覆盖新区间时不能移动 arrowPos，否则可能失去对之前区间的覆盖。
  • 与 435 题“无重叠区间”使用同一贪心骨架：都是按最早结束位置保留最大余地。

易错点总结

[!yellow]

  • 端点可能接近整数极值，Java 比较器不能靠相减判断大小，应使用 Integer.compare。
  • 新增箭的条件是 start > arrowPos，等于箭位仍属于闭区间命中。
  • 按左端点排序后直接使用同样的右端点放箭规则，没有保证该箭能留在更短的后续区间内。
  • 区间已覆盖时不要更新箭位，否则可能使箭离开之前已经负责覆盖的区间。
  • 读取第一个区间前需要处理空输入，避免访问不存在的元素。

相似题目

题目 难度 关联与区别
435. 无重叠区间 中等 同样按右端点贪心，原题选最多互不重叠区间，本题选最少位置命中全部区间。
56. 合并区间 中等 同样处理区间重叠，但并集相连不等于能被同一支箭穿过，本题要求存在共同交点。
646. 最长数对链 中等 按结束位置判断区间重叠并进行贪心选择；本题用最少位置覆盖所有区间，该题将数对连接视为不重叠区间选择。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/90181331
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！