如何用最少的箭射爆一排气球：贪心算法与哈希计数解法_网络技术

如何用最少的箭射爆一排气球：贪心算法与哈希计数解法

发布时间 - 2026-01-23 00:00:00 点击率：次

本文介绍解决“baloni”问题的核心思路——通过哈希表动态维护各高度剩余未匹配气球数量，利用“高度差为1”的连续性特征实现贪心匹配，时间复杂度 o(n)，空间复杂度 o(n)，正确高效地求出最少箭数。

该问题的本质是：每支箭从左向右水平射出，初始高度为某值 h，每击中一个气球后高度自动减 1；因此一支箭能击中的气球序列，其高度必须严格构成一个递减连续整数序列（如 5→4→3→2→1），且在原数组中按从左到右顺序出现。

关键观察在于：一支箭的路径等价于一条“高度递减链”。若某个气球高度为 h，它要么作为某条链的起点（需新增一支箭），要么恰好接在某个已存在的、高度为 h+1 的气球之后（即被同一支箭续上）。因此，我们应尽可能“复用”已有箭——每当遇到高度为 h 的气球时，优先尝试将其链接到尚未被消耗的、高度为 h+1 的气球之后。

这自然引出贪心策略：

从左到右遍历每个气球；
对当前气球高度 h，检查是否还有未匹配的 h+1 高度气球（即之前出现过、但尚未被后续气球接续的）；
若有，则消耗一个 h+1 气球（表示该箭延续至此），不新增箭；
无论是否匹配成功，当前气球 h 都成为一条潜在新链的起点，因此需计入 h 高度的待匹配计数中。

实现上，我们使用字典 d 记录各高度当前“待被接续”的气球数量（即作为某支箭中间节点或起点的候选）。遍历时：

若 d[h + 1] > 0，说明存在可延续的箭，执行 d[h + 1] -= 1；
然后 d[h] += 1，将当前气球加入待匹配池。

最终，字典中所有剩余计数值之和，即为必须作为“链起点”的气球数——也就是所需的最少箭数。

以下是完整、可直接提交的 Python 实现：

def min_arrows(balloons):
    # d[height] 表示当前有多少个高度为 height 的气球可作为箭的起点或中间节点
    d = {}
    for h in balloons:
        # 尝试将当前气球 h 接在高度为 h+1 的气球之后（复用已有箭）
        if d.get(h + 1, 0) > 0:
            d[h + 1] -= 1
        # 当前气球 h 成为新的潜在起点（或新链首）
        d[h] = d.get(h, 0) + 1
    return sum(d.values())

# 主程序
n = int(input().strip())
balloons = list(map(int, input().split()))
print(min_arrows(balloons))

✅ 正确性验证：以 [2, 1, 5, 4, 3] 为例 h=2：d{2:1} → 箭数暂计 1 h=1：发现 d[2]>0，消耗一个 2 → d{2:0, 1:1} h=5：d{2:0, 1:1, 5:1} h=4：d[5]>0，消耗 5 → d{2:0, 1:1, 5:0, 4:1} h=3：d[4]>0，消耗 4 → d{2:0, 1:1, 5:0, 4:0, 3:1} 最终 sum = 1 + 1 = 2，符合预期。

⚠️ 常见误区提醒：

❌ 不可排序原数组——顺序决定能否形成合法链；
❌ 不可原地修改输入——会破坏高度关系与遍历逻辑；
❌ 不可无条件累加箭数——必须基于“能否接续”做条件判断。

该解法简洁、高效、符合直觉，是处理此类“递减链覆盖”问题的经典范式。

# python

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】

上一篇：Wattpad网页版故事入口 Wattpad在线免费好书阅读

下一篇：2026南昌中小学寒假通知_2026年南昌中小学寒假起止日期

相关栏目网站优化
网络推广
网络技术
AI营销

最新文章 Sublime怎么一键压缩JS代码 Su sublime如何在搜索中使用正则表达式 Sublime如何设置透明窗口效果 Su mysql如何设计商品表结构_mysql css属性背景图不显示怎么办_通过检查路如何使用Golang实现排序_Golan 农历闰月是怎么回事_为合回归年加一月调整塑造《刺客信条》艾吉奥传奇的编剧离开育碧 1英里等于多少公里 1mile和km的换 css grid布局中行和列是如何定义的 PS批量旋转和翻转图片，快速校正图片方向 C# Swagger UI自定义方法 C OPPO手机九宫格和全键盘怎么切换_OP Go语言如何实现用户登录注册_Golan 1节飞行速度多少公里每小时 1节是多少公纸嫁衣8千子树第五章庙门怎么开启庙门 Laravel 多行数据编辑表单中实现逐明日之后如何提升钓鱼等级明日之后提升钓支付宝怎样查年度账单_支付宝年度账单查看 C# 多线程UI更新Dispatcher

上一篇：Wattpad网页版故事入口 Wattpad在线免费好书阅读

下一篇：2026南昌中小学寒假通知_2026年南昌中小学寒假起止日期