如何用最少箭数击破一排高度各异的气球：贪心 + 哈希计数解法

本文介绍解决“baloni”问题的最优算法——通过哈希表维护各高度剩余气球数，对每个气球尝试复用前一高度（+1）的箭路径，从而最小化新增箭数。时间复杂度 o(n)，无需排序或修改原数组。

该问题本质是求最少箭数，使得每支箭从左向右水平射出，初始高度为某整数 h，每击破一个气球后高度自动减 1（即下一支被击中的气球必须恰好位于高度 h−1）。因此，一支箭能连续击破的气球序列必须满足：从某个位置开始，其高度严格递减 1（如 5→4→3→2→1），且在数组中保持原有从左到右的相对顺序。

关键洞察在于：一支箭的轨迹可视为一条“高度递减链”，而每个气球只能被一条链覆盖；要最小化箭数，就应尽可能延长已有链，而非频繁新建。这提示我们采用贪心策略：对每个气球 h，优先尝试将其接续到一条“当前末端高度为 h+1”的箭链上（因为该链下一次可下降至 h）；若不存在这样的链，则必须发射一支新箭，以 h 为起始高度开启新链。

实现时无需显式构建链，只需用哈希表 d 记录「当前有多少条箭链的末端高度恰好为 key」。遍历每个气球高度 h 时：

• 若 d[h + 1] > 0，说明存在一条末端在 h+1 的链，可延伸至此气球 → 将 d[h + 1] 减 1，并将 d[h] 加 1（链末端更新为 h）；
• 否则，必须新增一支箭 → d[h] += 1。

最终，sum(d.values()) 即为所有未被接续、仍处于活跃状态的箭链数量，也就是最小箭数。

以下是完整可运行代码：

def min_arrows(balloons):
    from collections import defaultdict
    d = defaultdict(int)  # d[h] = 当前末端高度为 h 的箭链数量
    for h in balloons:
        if d[h + 1] > 0:
            d[h + 1] -= 1
        d[h] += 1
    return sum(d.values())

# 示例验证
print(min_arrows([2, 1, 5, 4, 3]))  # 输出: 2
print(min_arrows([5, 4, 3, 2, 1]))  # 输出: 1
print(min_arrows([1, 2, 3, 4, 5]))  # 输出: 5

注意事项：

• 绝对不要对输入数组排序（如原始错误代码），否则破坏左右顺序约束，导致逻辑失效；
• 不应原地修改 balloons 数组，所有状态应由辅助数据结构（如 defaultdi

  

  ct）独立维护；
• 使用 defaultdict(int) 可避免手动检查键是否存在，提升代码简洁性与鲁棒性；
• 该算法时间复杂度为 O(n)，空间复杂度为 O(H)，其中 H 是不同高度的数量，实际中非常高效。

此解法已通过 Kattis 平台全部测试用例，是解决 Baloni 问题的标准贪心范式。

# 将其  # 有多少  # 一支  # 已有  # 不应  # 要对  # 并将  # 数据结构  # int  # 算法  # 遍历  # 绝对不 

相关栏目： <？ｍｕｍａ $count = M('archives')->where(['typeid'=>$field['id']])->count(); ?> 【 AI推广<？ｍｕｍａ echo $count; ?> 】 <？ｍｕｍａ $count = M('archives')->where(['typeid'=>$field['id']])->count(); ?> 【 SEO优化<？ｍｕｍａ echo $count; ?> 】 <？ｍｕｍａ $count = M('archives')->where(['typeid'=>$field['id']])->count(); ?> 【 技术百科<？ｍｕｍａ echo $count; ?> 】 <？ｍｕｍａ $count = M('archives')->where(['typeid'=>$field['id']])->count(); ?> 【 谷歌推广<？ｍｕｍａ echo $count; ?> 】 <？ｍｕｍａ $count = M('archives')->where(['typeid'=>$field['id']])->count(); ?> 【 百度推广<？ｍｕｍａ echo $count; ?> 】 <？ｍｕｍａ $count = M('archives')->where(['typeid'=>$field['id']])->count(); ?> 【 网络营销<？ｍｕｍａ echo $count; ?> 】 <？ｍｕｍａ $count = M('archives')->where(['typeid'=>$field['id']])->count(); ?> 【 案例网站<？ｍｕｍａ echo $count; ?> 】 <？ｍｕｍａ $count = M('archives')->where(['typeid'=>$field['id']])->count(); ?> 【 精选文章<？ｍｕｍａ echo $count; ?> 】