跳至主要內容

LeetCode 452. 用最少数量的箭引爆气球——区间贪心的变体

老张2026/4/30大约 16 分钟

LeetCode 452. 用最少数量的箭引爆气球——区间贪心的变体

适读人群：Java中级工程师、算法进阶学习者 | 阅读时长：约20分钟 | 难度：中等

开篇故事

有一次在做游戏后台开发的时候，遇到了一个资源调度问题：某个地图上散布着很多怪物（每个怪物有活动范围），我们需要释放AOE技能（范围伤害），每次技能打击的是一条垂直线上的所有目标。问题变成：最少需要几次技能才能打到所有怪物？

这跟 LeetCode 452 的气球问题一模一样！每只气球代表一个区间（在该区间内任意位置射箭都能引爆），每支箭代表一条垂直线，问最少需要多少支箭引爆所有气球。

有趣的地方在于，这道题看起来和"无重叠区间"（LeetCode 435）非常像，但它们有一个微妙的区别：端点相等的处理方式不同。这道题端点相等时一支箭可以同时引爆两个气球（因为箭在 x = end 位置可以穿过两个气球），而 435 题端点相等不算重叠。这个细节决定了代码层面的差异。今天我们把这道题和 435 题的关系彻底理清楚。

一、题目解析

题目： 有一些球形气球贴在一堵用 XY 平面表示的墙面上。气球的位置用整数数组 points 表示，其中 points[i] = [xstart, xend] 表示水平直径从 xstart 到 xend 的气球。你不知道气球的确切 y 坐标。一支弓箭可以沿着 x 轴从不同点完全垂直地射出，从一个点 x 处射出的箭，若有一个气球的 xstart <= x <= xend，则该气球会被引爆。可以射出的弓箭数量没有限制，但每支箭一旦被射出之后，可以无限前进。我们想找到使得所有气球全部被引爆所需的弓箭的最小数量，返回射爆所有气球所必须射出的最小弓箭数。

示例：

  • 输入：points = [[10,16],[2,8],[1,6],[7,12]]，输出：2 （第一支箭在 x=6 引爆[1,6],[2,8]，第二支箭在 x=11 引爆[10,16],[7,12]）
  • 输入：points = [[1,2],[3,4],[5,6],[7,8]]，输出：4（没有重叠，每个气球需要一支箭）
  • 输入：points = [[1,2],[2,3],[3,4],[4,5]]，输出：2（端点相交的气球可以一箭引爆）

关键差异（与 LeetCode 435 比较）：

题目端点相等贪心目标
LeetCode 435不算重叠最多保留不重叠区间（最少移除）
LeetCode 452算重叠（一箭穿两球）最少箭数覆盖所有区间

问题等价转化： 最少需要多少支箭 = 最多有多少个"互不能被同一支箭覆盖的气球组"。

而两个气球不能被同一支箭覆盖，当且仅当它们的区间不相交（注意：端点相等时它们可以被同一支箭覆盖，所以"不相交"的严格条件是 xend_a < xstart_b，即结束严格小于开始）。

二、解法一：动态规划（理解最优结构）

思路

定义"一组气球可以被同一支箭引爆"等价于这些气球有一个公共交叉点。将问题转化为：找最少数量的"公共交叉点"覆盖所有气球，等价于将气球分成最少的组，每组内所有气球有公共交叉。

这可以用 DP 来模拟，但由于贪心方案更优，DP 主要作为理解问题的工具。

代码（DP 模拟）

import java.util.Arrays;

public class Solution_DP {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) return 0;
        // 按右边界排序
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
        
        int n = points.length;
        // dp[i] = 引爆前i+1个气球所需最少箭数
        int[] dp = new int[n];
        dp[0] = 1;
        int groupEnd = points[0][1]; // 当前箭能覆盖的最右位置
        
        for (int i = 1; i < n; i++) {
            if (points[i][0] <= groupEnd) {
                // 当前气球可以被同一支箭覆盖，更新公共区间右端点
                groupEnd = Math.min(groupEnd, points[i][1]);
                dp[i] = dp[i-1];
            } else {
                // 需要新的一支箭
                groupEnd = points[i][1];
                dp[i] = dp[i-1] + 1;
            }
        }
        
        return dp[n-1];
    }
}

复杂度分析

  • 时间复杂度： O(n log n)，排序主导。
  • 空间复杂度： O(n)，dp 数组（可优化为 O(1) 只记前一个值）。

三、解法二：按右边界贪心（核心解法）

思路

贪心策略： 按气球右边界升序排序，每次在当前"最紧的"右边界处射箭，这样可以覆盖尽可能多的气球。

正确性证明：

设气球按右边界排序为 b1, b2, ..., bn（end1 <= end2 <= ... <= endn）。

贪心第一步：在 end1 处射箭。为什么不在别处射？

  • 若在 end1 右边射（位置 p > end1）：所有能被 p 覆盖的气球，其右边界 >= p > end1，且左边界 <= p。但 b1 的右边界 = end1 < p，所以 b1 无法被覆盖，需要额外一支箭。这不比在 end1 处射更好。
  • 若在 end1 左边射（位置 p < end1）：覆盖的气球必须满足 start_i <= p < end1，这是 end1 处所覆盖气球的子集（凡是满足 start_i <= p 的也满足 start_i <= end1）。所以在 end1 左边射，覆盖的气球只少不多。

因此，在 end1 处射箭是局部最优，也不会使全局变差（交换论证）。

射完第一箭后，移除所有被覆盖的气球，对剩余气球重复上述过程。

关键细节：端点相等处的重叠判断

// 气球 i 可被当前箭覆盖的条件
// 当前箭位置在 arrowPos，气球区间 [start_i, end_i]
// 条件：start_i <= arrowPos <= end_i
// 即 start_i <= arrowPos（含等号）

// 代码实现：贪心扫描时，如果当前气球左边界 <= arrowPos，则被覆盖
if (points[i][0] <= arrowPos) {  // 注意是 <=，端点相等时也被覆盖
    // 跳过，继续看下一个气球
} else {
    // 需要新的一支箭
    arrowPos = points[i][1];
    arrows++;
}

代码

import java.util.Arrays;

public class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) return 0;
        
        // 按右边界升序排序（端点相等时顺序无所谓）
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], 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];
            }
            // 否则：当前气球被当前箭覆盖（start_i <= arrowPos），继续
        }
        
        return arrows;
    }
}

Mermaid 图：贪心过程

复杂度分析

  • 时间复杂度： O(n log n)，排序主导，线性扫描 O(n)。
  • 空间复杂度： O(1)（不含排序栈空间）。

四、解法三：等价转化为"最多不重叠区间"

思路

关键洞察： 最少需要的箭数 = 气球中最多"互不相交"的气球数。

因为如果有 k 个互不相交的气球，每个气球都必须有自己专属的一支箭；反过来，如果找到了 k 支箭能覆盖所有气球，那这 k 支箭对应的"核心气球"就是互不相交的。

与 LeetCode 435 的区别：

  • LeetCode 435 的"不重叠"：end_a < start_b（严格小于，端点相等算重叠）
  • 本题的"互不相交"：end_a < start_b（严格小于，端点相等时一箭可同时覆盖）

所以这里的严格定义都是 end_a < start_b，两题在这个判断上是一样的！区别在于：

  • LeetCode 435 问"最少移除几个让剩余不重叠"，其"不重叠"定义是 end_a <= start_b（>=号）
  • 本题的"互不相交"也是 end_a < start_b（严格小于号）

代码（转化为 435 题的框架）：

import java.util.Arrays;

public class Solution_V2 {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) return 0;
        
        // 按右边界排序
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
        
        // 统计最多不相交气球数
        // 不相交条件：points[i][0] > prevEnd（严格大于，端点相等可以共用一支箭）
        int count = 1;
        int prevEnd = points[0][1];
        
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > prevEnd) { // 严格大于：端点相等不算"独立"
                count++;
                prevEnd = points[i][1];
            }
        }
        
        return count;
    }
}

注意这里和解法二的代码几乎相同，印证了两种视角的等价性。

复杂度分析

  • 时间复杂度： O(n log n)
  • 空间复杂度： O(1)

五、举一反三

对比三道区间贪心题

LeetCode 435（不重叠区间）：
- 目标：移除最少区间，使剩余不重叠（end_a <= start_b 算不重叠）
- 返回值：n - maxNonOverlapping
- 贪心：按结束时间排序，end_a <= start_b 继续，否则移除当前（更新end_a）

LeetCode 452（气球引爆）：
- 目标：最少箭数覆盖所有区间（end_a < start_b 才算完全不相交）
- 返回值：需要箭数（等于不相交区间组数）
- 贪心：按结束时间排序，start_b > end_a 才需要新箭

LeetCode 56（合并区间）：
- 目标：合并所有重叠区间
- 按开始时间排序，右边界取最大值合并

代码层面的唯一差异： >= 和 > 的区别

// 435 题：端点相等不重叠，用 >= 判断"可以保留"
if (curr[0] >= prevEnd) { keep++; prevEnd = curr[1]; }

// 452 题：端点相等可以共用一支箭，用 > 判断"需要新箭"
if (curr[0] > prevEnd) { arrows++; prevEnd = curr[1]; }

六、踩坑实录

坑一：端点相等的判断符号写反

这道题最容易混淆的就是端点相等的处理。题目说箭在 xend 处可以引爆气球（包含端点），所以 points[i][0] == prevEnd 时，当前气球可以被当前箭覆盖，不需要新箭。

// 错误：用 >= 判断需要新箭，把端点相等的情况归为"需要新箭"
if (points[i][0] >= arrowPos) { arrows++; arrowPos = points[i][1]; }

// 正确：用 > 判断需要新箭，端点相等时不需要新箭
if (points[i][0] > arrowPos) { arrows++; arrowPos = points[i][1]; }

如果写成 >=，测试用例 [[1,2],[2,3]] 的输出会是 2（应该是 1）。

坑二：比较器溢出问题

气球坐标范围是 -2^31 到 2^31 - 1，直接用减法比较会溢出：

// 危险：Integer.MIN_VALUE - Integer.MAX_VALUE 溢出！
Arrays.sort(points, (a, b) -> a[1] - b[1]);

// 安全：
Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));

坑三：按左边界排序能否AC？

实验发现，按左边界排序也能写出正确解，但逻辑要复杂很多（需要维护"当前组的公共区间"而不是单纯的右边界）。按右边界排序的算法更简洁，是标准做法。不要因为直觉上"从左到右扫描"就按左边界排序。

坑四：数组越界（空数组）

// 必须在开头处理空数组
if (points.length == 0) return 0;

// 不然 points[0][1] 会越界

七、总结

LeetCode 452 是区间贪心变体的典型代表，它与 LeetCode 435 高度相似，差异只在端点相等的处理上。学完这道题，你应该能清楚地说出：

  1. 为什么按右边界排序：每次在最紧的右边界射箭，为后续区间保留最大可能的覆盖机会。
  2. 端点相等的处理：> 还是 >= 取决于题目对"边界重叠"的定义，要仔细读题。
  3. 与 435 题的等价关系：最少箭数 = 最多"互不相交"气球组数 = 去掉那些"可以共享箭"的气球后的独立计数。
解法时间复杂度空间复杂度说明
DP 模拟O(n log n)O(n)理解最优子结构
按右边界贪心O(n log n)O(1)标准推荐解
等价转化（435框架）O(n log n)O(1)强调与435的关系

补充深入讲解：气球问题的多角度理解与面试技巧

从覆盖点到区间相交：数学本质

引爆气球问题有一个非常优雅的数学等价表述，理解这个等价关系有助于加深对这类问题的理解。

一支箭在位置 x 处射出，等价于放置一个点 x 在数轴上。一个气球 [xstart, xend] 被一支箭引爆，等价于点 x 在区间 [xstart, xend] 内（包括端点）。"最少几支箭引爆所有气球"等价于"在数轴上放置最少的点，使每个区间 [xstart, xend] 内至少包含一个点"。

这种等价表述在形式上叫做"区间覆盖问题"：给定一组区间，找最少的点使每个区间都被覆盖。这类问题在图论和组合优化中有很深的理论背景，本质上是集合覆盖问题的一维特例。

对偶关系： 有趣的是，"最少的点覆盖所有区间"和"最多的互不相交区间"有一个深刻的对偶关系（Helly 定理的一维版本）：在一维情况下，最少的点覆盖数等于最大的"互不相交"区间组的大小。这不是巧合，而是有严格数学证明的定理。

理解了这个对偶关系，你会发现 LeetCode 452（引爆气球）和 LeetCode 435（无重叠区间）本质上在求同一件事，只是描述方式不同。这就是为什么两道题的代码如此相似，只有一个比较符号的差异。

端点相等的一箭双雕现象

题目说明当 xstart <= x <= xend 时，气球被引爆，这意味着端点处也能被引爆。因此，如果两个气球恰好端点相邻（第一个气球的右端点等于第二个气球的左端点），一支箭恰好射在这个端点处，可以同时引爆两个气球。

这就是为什么代码中的判断是 points[i][0] > arrowPos（严格大于），而不是 >= arrowPos：当 points[i][0] == arrowPos 时，当前箭恰好在这个气球的左端点上，气球被引爆，不需要新的箭。

来看一个具体的例子：气球 [1,3] 和 [3,6]，如果在 x=3 处射箭，两个气球都被引爆（3 在 [1,3] 的范围内，也在 [3,6] 的范围内）。所以这两个气球只需要一支箭，而不是两支。

在实际面试中，这个端点细节是常见的送分题和送命题：如果面试官问"你的代码能处理端点相等的情况吗"，你必须能清晰地解释为什么用 > 而不是 >=。

贪心策略的直觉理解

按右边界排序，每次在最紧的右边界处射箭——这个策略的直觉是什么？

想象一下，你站在数轴的左端，从左往右看各个气球。排序后，你先看到右边界最小的那个气球。这个气球的右边界是所有气球中"最早结束"的，如果你不在这里或更左的位置射箭，这个气球就永远射不到了（它的右边界是最小的）。因此，你必须在这个气球的右边界处（或更左的位置）射箭。

在它的右边界处射箭，是最优选择，因为可以"捎带"引爆所有开始时间也在此范围内的其他气球。如果在更左的位置射，虽然也能引爆这个气球，但"捎带"的其他气球只会更少（因为其他气球的开始时间可能在你选择的位置的右边）。

因此，每次在"最紧约束"的气球的右边界处射箭，是局部最优且全局最优的策略。

与现实问题的对应

引爆气球这类"最少覆盖点"问题在工程中的应用场景包括：

无线网络基站覆盖： 给定一批需要被覆盖的信号范围区间，最少需要多少个基站（每个基站覆盖数轴上一个点）才能覆盖所有区间？这是引爆气球的直接应用。

代码行覆盖测试： 给定一批测试用例，每个用例覆盖一段连续的代码行（区间），最少选几个测试用例可以覆盖某段代码的所有行？同样是覆盖点问题。

时间序列数据采样： 给定若干需要采样的时间区间，最少在几个时间点采样，可以使每个时间区间都至少被采样一次？这在监控系统的采样策略设计中经常遇到。

面试变题：如果每支箭有长度怎么办？

变形题：每支箭不再是无限细的一条线，而是有一定宽度 w（即一支箭从 x 射出，覆盖 [x, x+w] 的范围），最少需要多少支箭引爆所有气球？

这个变形的贪心策略需要调整：按右边界排序后，每次选择当前未引爆气球的最左可能位置（即使箭恰好能引爆这个气球的射出点 = 右边界 - w），然后引爆所有在 [射出点, 射出点+w] 内的气球。这是一个略复杂的贪心变体，有兴趣的同学可以作为练习。

按右边界排序的深层原因

为什么引爆气球（LeetCode 452）按右边界排序而不是左边界排序？这个问题值得深入思考。

核心在于贪心选择的参照物是什么。我们每次射出一支箭，箭的位置由当前"最紧迫"的气球决定。"最紧迫"的气球是右边界最小的那个——它对箭的位置约束最紧，如果不在它的范围内射箭，这个气球就必须单独用一支箭，浪费了一次机会。

按右边界排序后，每次处理的是当前右边界最小的气球，在它的右边界处射箭是最优的：既满足了这个最紧迫的气球，又尽可能地延迟了箭的位置（越靠右，覆盖后续气球的机会越多）。

如果按左边界排序，每次处理的是左边界最小的气球，但这个气球的右边界可能很大，在它的右边界射箭会覆盖很多后续气球，但也可能浪费了本可以更早射箭的机会。这种情况下，贪心策略的正确性分析会复杂得多，不如按右边界排序清晰直观。

这个"按结束时间排序，在当前最紧约束处做决策"的模式，在贪心算法中普遍适用：区间调度（LeetCode 435）、活动选择问题（经典贪心）都遵循同样的思路。

编辑此页
最近更新:
贡献者: xiaozhangge