漯河市网站建设_网站建设公司_展示型网站_seo优化

哈喽各位，我是前端小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)

1. 特判：如果数组为空，返回 0。

2. 排序：按start(下标0) 升序排列。

3. 初始化：arrows = 1(只要有气球，至少要一箭)。

4. 遍历：从第 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 必须用新箭了。

复杂度分析

• 时间复杂度：$O(N \log N)$。因为有排序。遍历只需要 $O(N)$。

• 空间复杂度：$O(1)$。除了排序可能需要的栈空间，我们没有使用额外数组。

总结：区间问题的通解

这道题展示了区间问题的标准模板：

1. 排序（通常按 Start 排序）。

2. 判断重叠（Start vs PrevEnd）。

3. 更新边界（取 Min 还是 Max 看具体需求）。

下一题预告：无重叠区间

如果你理解了这一题，那么下一题 LC 435. 无重叠区间 你只需要改两行代码就能通过。

题目问：给定一堆区间，最少移除几个区间，才能让剩下的区间都不重叠？

思考一下：

“最少移除几个”是不是等价于“最多保留几个（不重叠的）”？

而“最多保留几个不重叠的区间”是不是和“最少用几支箭引爆所有气球”有着某种神秘的数学联系？（提示：其实就是一模一样的题！）

下期见！