当前位置：首页 > news >正文

贪心算法专题(十一)：一箭双雕的快乐——「用最少数量的箭引爆气球」

news 2026/3/27 5:03:04

哈喽各位，我是前端小L。

欢迎来到贪心算法专题第十一篇！

想象一下，墙上贴着一排气球，每个气球都有一个水平覆盖范围 [start, end]。

你是神射手，可以垂直射出一支箭。只要箭的 X 坐标在气球的覆盖范围内，气球就会爆炸。

贪心目标：找准所有气球重叠最密集的地方射箭，争取用最少的箭引爆所有气球。

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

https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/

题目分析：

输入：points数组，元素为[xstart, xend]。
输出：最少箭数。

例子：[[10,16], [2,8], [1,6], [7,12]]

气球 A:1~6
气球 B:2~8
气球 C:7~12
气球 D:10~16

如果我们乱射，可能需要 4 支箭。

但如果我们精打细算：

在x=6射一箭：引爆 A(1~6) 和 B(2~8)。
在x=11射一箭：引爆 C(7~12) 和 D(10~16)。
共需 2 支箭。

核心思维：寻找“重叠区间”

我们要想一箭穿透多个气球，这几个气球必须在垂直方向上有重叠。

问题转化为：如何找到这组气球的公共重叠区域？

第一步：排序

既然是区间，肯定要让它们有序排列才能方便判断。我们通常按起始位置 (Start) 从小到大排序。

排序前：[[10,16], [2,8], [1,6], [7,12]]
排序后：[1,6], [2,8], [7,12], [10,16]

第二步：遍历与更新边界

我们拿第一支箭去瞄准第一个气球 [1, 6]。理论上，这支箭可以射在 1 到 6 之间的任何位置。

为了让这支箭能射中后面更多的气球，我们应该尽可能往右边射（延迟射出），但不能超过 6。

看第二个气球[2, 8]：
- 它的起始位置2小于第一个气球的结束位置6。说明有重叠！
- 这支箭可以同时射中这两个。
- 关键点：但这支箭的射击范围被压缩了。它必须在[1, 6]里，也必须在[2, 8]里。所以这支箭最远只能射到min(6, 8) = 6。
- 更新当前重叠组的右边界：right = 6。
看第三个气球[7, 12]：
- 它的起始位置7大于当前重叠组的右边界6。
- 说明断档了！前面那支箭最远只能射到 6，根本够不着 7。
- 决策：前面的气球结算，必须射出一支箭了（arrows++）。然后我们拿出一支新箭，瞄准这个新气球[7, 12]。

算法流程 (JavaScript)

特判：如果数组为空，返回 0。
排序：按start(下标0) 升序排列。
初始化：arrows = 1(只要有气球，至少要一箭)。
遍历：从第 2 个气球 (i=1) 开始遍历。
- 如果当前气球.start > 上一个气球.end：
  - 无重叠，需要一支新箭。arrows++。
- 如果当前气球.start <= 上一个气球.end：
  - 有重叠，省下一支箭。
  - 核心操作：更新当前气球的右边界（模拟求交集）。
  - 当前气球.end = Math.min(当前气球.end, 上一个气球.end)。
  - 注：这里我们直接修改数组元素的 end 值，让它作为“当前重叠组的最小右边界”传递给下一次比较。

代码实现

JavaScript

/** * @param {number[][]} points * @return {number} */ var findMinArrowShots = function(points) { if (points.length === 0) return 0; // 1. 按起始位置升序排列 // 注意：a[0] - b[0] 可能会溢出(在C++中)，但在JS中 number 是浮点数，一般没事 // 稳妥写法是 (a, b) => a[0] - b[0] points.sort((a, b) => a[0] - b[0]); let arrows = 1; // 至少需要一支箭 // 2. 从第二个气球开始遍历 for (let i = 1; i < points.length; i++) { // 如果当前气球的左边界 > 上一个气球(修正后)的右边界 // 说明完全不沾边，必须新加一支箭 if (points[i][0] > points[i - 1][1]) { arrows++; } else { // 说明有重叠，这支箭可以继续穿透 // 但是，为了能穿透这两个气球，箭必须射在两者较小的那个右边界之内 // 我们更新当前气球的右边界，作为这一组重叠气球的“最远射击位置” points[i][1] = Math.min(points[i][1], points[i - 1][1]); } } return arrows; };

深度辨析：为什么要`Math.min`？

假设气球是A: [1, 10](很大),B: [2, 3](很小且在A内部)。

排序后：A 在前，B 在后。
遍历到 B 时，B.start(2) <= A.end(10)，有重叠。
如果我们不更新边界，继续用A.end(10)跟后面的气球比。
假设后面有个气球C: [4, 5]。
C.start(4) <= A.end(10)，看起来好像能一箭穿 A、B、C？
错！你的箭如果要穿过 B，就必须在[2, 3]之间射。如果你在4射箭，虽然能中 A 和 C，但 B 就漏了。
所以，一旦发现重叠，这支箭的有效射击范围就瞬间缩小到了重叠区域（即右边界取最小值3）。这样对比 C 的时候，4 > 3，我们就知道 C 必须用新箭了。