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

大家好，我是展菲，目前在上市企业从事人工智能项目研发管理工作，平时热衷于分享各种编程领域的软硬技能知识以及前沿技术，包括iOS、前端、Harmony OS、Java、Python等方向。在移动端开发、鸿蒙开发、物联网、嵌入式、云原生、开源等领域有深厚造诣。

图书作者：《ESP32-C3 物联网工程开发实战》
图书作者：《SwiftUI 入门，进阶与实战》
超级个体：COC上海社区主理人
特约讲师：大学讲师，谷歌亚马逊分享嘉宾
科技博主：华为HDE/HDG

我的博客内容涵盖广泛，主要分享技术教程、Bug解决方案、开发工具使用、前沿科技资讯、产品评测与使用体验。我特别关注云服务产品评测、AI 产品对比、开发板性能测试以及技术报告，同时也会提供产品优缺点分析、横向对比，并分享技术沙龙与行业大会的参会体验。我的目标是为读者提供有深度、有实用价值的技术洞察与分析。

展菲：您的前沿技术领航员
👋 大家好，我是展菲！
📱 全网搜索“展菲”，即可纵览我在各大平台的知识足迹。
📣 公众号“Swift社区”，每周定时推送干货满满的技术长文，从新兴框架的剖析到运维实战的复盘，助您技术进阶之路畅通无阻。
💬 微信端添加好友“fzhanfei”，与我直接交流，不管是项目瓶颈的求助，还是行业趋势的探讨，随时畅所欲言。
📅 最新动态：2025 年 3 月 17 日
快来加入技术社区，一起挖掘技术的无限潜能，携手迈向数字化新征程！

摘要

这道题是一个非常经典、也非常容易被「想复杂」的题。

表面上看：

• 有一堆区间
• 要用最少的点去覆盖所有区间

本质上：

• 这是一个标准的区间贪心问题
• 而且是「按右边界排序」这一类的代表题

如果你以后在项目里遇到：

• 时间段资源复用
• 区间合并
• 最少触发次数、最少请求次数

那这道题的思路，基本可以原封不动地搬过去用。

描述

题目给了一个二维数组points：

points[i] = [xstart, xend]

表示一个气球在 x 轴上的覆盖范围。

规则是：

• 你可以在任意一个x位置射箭
• 如果xstart ≤ x ≤ xend，这个气球就会被引爆
• 一支箭可以引爆多个气球
• 箭的数量没有限制
• 要求：用最少的箭，引爆所有气球

题解答案（核心思路）

这道题的正确打开方式只有一句话：

尽量用一支箭，覆盖尽可能多的气球。

怎么做到？

关键策略

1. 按气球的右边界排序

2. 第一支箭，射在第一个气球的xend

3. 后面的气球：

   • 如果它的xstart <= 当前箭的位置，说明能一起引爆
   • 否则，必须再射一支箭

为什么是按右边界排序？

因为：

• 右边界越靠左，能“兼容”的区间越少
• 优先处理这些区间，能保证后面的选择空间最大

这是贪心算法里非常典型的一种「局部最优保证全局最优」的场景。

题解代码（Swift 可运行 Demo）

classSolution{funcfindMinArrowShots(_points:[[Int]])->Int{ifpoints.isEmpty{return0}// 1. 按右边界排序letsortedPoints=points.sorted{$0[1]<$1[1]}// 2. 至少需要一支箭vararrows=1// 当前箭射在的位置varcurrentEnd=sortedPoints[0][1]// 3. 遍历剩余气球foriin1..<sortedPoints.count{letstart=sortedPoints[i][0]// 如果当前气球和当前箭没有重叠ifstart>currentEnd{arrows+=1currentEnd=sortedPoints[i][1]}}returnarrows}}

题解代码分析

1. 排序是整个解法的灵魂

letsortedPoints=points.sorted{$0[1]<$1[1]}

我们只关心一件事：

• 谁先「结束」

因为：

• 箭射在xend，是当前能兼容最多气球的位置

2. 为什么初始箭数是 1？

vararrows=1varcurrentEnd=sortedPoints[0][1]

只要有气球，就至少需要一支箭。
第一支箭直接射在第一个气球的右边界，这是当前最优选择。

3. 核心判断逻辑

ifstart>currentEnd{arrows+=1currentEnd=sortedPoints[i][1]}

这句判断非常重要：

• start <= currentEnd

  • 当前箭还能打到这个气球

• start > currentEnd

  • 无论怎么射，都得新来一支箭

4. 为什么不用管 y 坐标？

题目已经帮我们简化了问题：

• 箭是「完全垂直」射出
• y 坐标不影响是否命中

所以这是一个纯一维区间问题。

示例测试及结果

示例 1

letsolution=Solution()letpoints1=[[10,16],[2,8],[1,6],[7,12]]print(solution.findMinArrowShots(points1))

输出：

2

示例 2

letpoints2=[[1,2],[3,4],[5,6],[7,8]]print(solution.findMinArrowShots(points2))

输出：

4

每个区间都不重叠，只能一箭一个。

示例 3

letpoints3=[[1,2],[2,3],[3,4],[4,5]]print(solution.findMinArrowShots(points3))

输出：

2

边界相接是可以共用一支箭的。

实际场景结合

这个模型在真实项目里非常常见，比如：

• 批量任务调度

  • 一次任务可以覆盖多个时间窗口

• 接口请求合并

  • 尽量用一次请求，覆盖多个需求

• 资源释放策略

  • 用最少的操作，释放最多的资源

只要你看到：

• 区间
• 覆盖
• 最少次数

第一反应就应该是：
是不是可以排序 + 贪心？

时间复杂度

• 排序：O(n log n)
• 单次遍历：O(n)

总体时间复杂度：

O(n log n)

这是这类问题的最优解法级别。

空间复杂度

• 排序使用额外数组：O(n)
• 其他变量常量级

空间复杂度：

O(n)

总结

LeetCode 452 是一道：

• 非常经典的贪心题
• 非常适合用来建立「区间问题直觉」
• 面试和实际开发都很常见的模型题