Skip to main content

用最小数量的箭引爆气球

· 4 min read
Eureka X
Eureka X
Mr.Nobody

力扣面试经典——452题​

💡 参考代码：​

#include <stdio.h>
#include <stdlib.h>

// 比较函数，用于按气球右端点升序排序
// 修复整数溢出问题：避免直接相减可能导致的溢出
int compare(const void *a, const void *b) {
    int *balloonA = *(int **)a;
    int *balloonB = *(int **)b;
    
    // 使用long long类型避免溢出，或者使用比较而非相减
    if (balloonA[1] < balloonB[1]) {
        return -1;
    } else if (balloonA[1] > balloonB[1]) {
        return 1;
    } else {
        return 0;
    }
}

/**
 * @brief 计算引爆所有气球所需的最小弓箭数
 * 
 * @param points 气球坐标数组，points[i] = [xstart, xend] 表示气球水平直径
 * @param pointsSize 气球数量
 * @param pointsColSize 每个气球坐标的列数（始终为2）
 * @return int 所需最少弓箭数
 */
int findMinArrowShots(int** points, int pointsSize, int* pointsColSize) {
    // 边界条件：如果没有气球，返回0
    if (pointsSize == 0) {
        return 0;
    }
    
    // 按照气球右端点升序排序
    qsort(points, pointsSize, sizeof(int *), compare);
    
    // 初始化箭的数量为1（至少需要一支箭）
    int arrows = 1;
    
    // 记录当前箭的位置（初始化为第一个气球的右端点）
    int arrowPos = points[0][1];
    
    // 遍历所有气球
    for (int i = 1; i < pointsSize; i++) {
        // 如果当前气球的左端点大于箭的位置，说明无法被当前箭引爆
        if (points[i][0] > arrowPos) {
            // 需要增加一支新箭
            arrows++;
            // 将箭的位置更新为当前气球的右端点
            arrowPos = points[i][1];
        }
        // 如果当前气球的左端点小于等于箭的位置，则可以被当前箭引爆，无需额外操作
    }
    
    return arrows;
}

📖 总结：​

点击展开题目总结

🤔 题目名称：用最少数量的箭引爆气球

1️⃣ 题目核心信息​

🎯 功能描述：计算引爆所有气球所需的最少弓箭数量

📥 输入输出：

  • 输入：points - 气球坐标数组，pointsSize - 气球数量，pointsColSize - 每个气球坐标的列数
  • 输出：引爆所有气球所需的最少弓箭数

2️⃣ 实现原理​

💡 核心思路：贪心算法 + 排序

📋 实现步骤：

  1. 按照气球右端点进行升序排序
  2. 将第一支箭射在第一个气球的右端点
  3. 遍历剩余气球，如果当前气球左端点超过箭的位置，则需要新增箭
  4. 更新箭的位置为当前气球的右端点

3️⃣ 关键点解析​

🎯 代码技巧​

  • 使用贪心策略，每次将箭射在气球右端点以引爆最多气球
  • 排序时避免整数溢出，使用比较而非相减
  • 时间复杂度优化到 O(n log n)

4️⃣ 使用场景​

✅ 适用情况：​

  • 区间调度问题
  • 资源分配优化
  • 覆盖问题

⚠️ 前提条件：​

  • 气球坐标为有效整数
  • 气球数量大于0

5️⃣ 复杂度分析​

  • ⏱️ 时间复杂度：O(n log n) - 主要消耗在排序上
  • 💾 空间复杂度：O(1) - 只使用常数额外空间

6️⃣ 注意事项​

🚩 边界情况：​

  • 空数组
  • 单个气球
  • 极值坐标

💥 易错点：​

  • 比较函数中的整数溢出
  • 贪心策略的正确性证明
  • 边界条件处理

7️⃣ 补充说明​

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

第一步：排序​

原始数组：[[10,16],[2,8],[1,6],[7,12]] 按右端点排序后：[[1,6],[2,8],[7,12],[10,16]]

第二步：逐步处理​

  1. 处理第一个气球 [1,6]：

    • arrows = 1（初始箭数）
    • arrowPos = 6（箭的位置设为第一个气球的右端点）

  2. 处理第二个气球 [2,8]：

    • 检查：2 <= 6（气球左端点 <= 箭位置）
    • 结论：可以被当前箭引爆，无需新增箭
    • arrows = 1，arrowPos = 6

  3. 处理第三个气球 [7,12]：

    • 检查：7 > 6（气球左端点 > 箭位置）
    • 结论：无法被当前箭引爆，需要新增箭
    • arrows = 2（箭数增加）
    • arrowPos = 12（箭位置更新为当前气球右端点）

  4. 处理第四个气球 [10,16]：

    • 检查：10 <= 12（气球左端点 <= 箭位置）
    • 结论：可以被当前箭引爆，无需新增箭
    • arrows = 2，arrowPos = 12

第三步：返回结果​

最终返回 arrows = 2，即需要2支箭。

图解说明​

排序后气球分布：
[1---6]     第1支箭位置(6)可引爆
  [2---8]   
      [7----12]  第2支箭位置(12)可引爆
         [10----16]

箭1在位置6：引爆[1,6]和[2,8]
箭2在位置12：引爆[7,12]和[10,16]

这就是算法的完整执行过程。通过贪心策略，每次都尽可能多地引爆气球，从而达到最少箭数的目标。

加载评论中...