LeetCode 452 - 用最少数量的箭引爆气球（Minimum Number of Arrows to Burst Balloons）

问题描述

有一些球形气球贴在一堵用 XY 平面表示的墙上。墙上的气球用一个二维数组 points 表示，其中 points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend 之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend，且满足 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：排序

按照每个气球的右端点 points[i][1] 进行升序排序。

步骤 2：贪心选择

• 初始化箭数 ans = 1（至少需要一支箭）
• 记录第一支箭的射击位置为第一个气球的右端点 maxRight = points[0][1]

步骤 3：遍历处理

对于每个后续气球：

• 如果当前气球的左端点 point[0] > maxRight，说明当前箭无法射中这个气球
• 需要射出新的一箭：ans++，并更新射击位置 maxRight = point[1]
• 否则，当前箭可以射中这个气球，无需额外操作

为什么按右端点排序？

按右端点排序的原因是：贪心地选择尽可能靠右的位置射箭，能够覆盖更多的气球。

考虑两个重叠的区间 [a1, b1] 和 [a2, b2]，其中 b1 ≤ b2：

• 如果在 b1 处射箭，可以同时射中两个气球
• 如果在 b2 处射箭，只能射中第二个气球
• 因此选择 b1（较小的右端点）更优

实现细节

排序策略

sort.Slice(points, func(i, j int) bool {
    return points[i][1] < points[j][1]  // 按右端点升序排序
})

贪心判断

对于每个气球，判断其左端点是否大于当前箭的射击位置：

• point[0] > maxRight：需要新箭
• point[0] ≤ maxRight：当前箭可以射中

执行示例

以 points = [[10,16],[2,8],[1,6],[7,12]] 为例：

1. 排序后：[[1,6],[2,8],[7,12],[10,16]]
2. 初始状态：ans = 1, maxRight = 6
3. 处理 [2,8]：2 ≤ 6，当前箭可射中，无需新箭
4. 处理 [7,12]：7 > 6，需要新箭，ans = 2, maxRight = 12
5. 处理 [10,16]：10 ≤ 12，当前箭可射中，无需新箭
6. 结果：ans = 2

代码实现

func findMinArrowShots(points [][]int) int {
    // 按右端点升序排序
    sort.Slice(points, func(i, j int) bool {
        return points[i][1] < points[j][1]
    })
    
    ans := 1                    // 至少需要一支箭
    maxRight := points[0][1]    // 第一支箭的射击位置
    
    // 遍历剩余气球
    for _, point := range points {
        if point[0] > maxRight {    // 当前箭无法射中这个气球
            ans++                   // 需要新箭
            maxRight = point[1]     // 更新射击位置
        }
        // 否则当前箭可以射中，继续下一个气球
    }
    
    return ans
}

复杂度分析

时间复杂度：$O(n \log n)$

• 排序操作需要 $O(n \log n)$ 时间
• 遍历数组需要 $O(n)$ 时间
• 总体时间复杂度为 $O(n \log n)$

空间复杂度：$O(1)$

• 只使用了常数个额外变量
• 排序是原地进行的（Go 的 sort.Slice 是原地排序）

关键收获

核心算法概念

1. 贪心算法：在每一步都做出当前看起来最优的选择
2. 区间重叠问题：通过排序和贪心策略解决
3. 排序策略的选择：按右端点排序是关键

常见陷阱

1. 排序方向错误：必须按右端点升序排序，不是左端点
2. 边界条件处理：注意 point[0] > maxRight 的判断条件
3. 初始化错误：箭数应该初始化为 1，不是 0

相关问题

• LeetCode 435: 无重叠区间
• LeetCode 253: 会议室 II
• LeetCode 56: 合并区间

算法模板

这类区间重叠问题的通用解法：

1. 根据问题特点选择排序策略（左端点或右端点）
2. 贪心地处理每个区间
3. 维护必要的状态信息（如当前覆盖范围）