TNotes.leetcode

Appearance

⏰0452. 用最少数量的箭引爆气球【中等】

0452. 用最少数量的箭引爆气球【中等】 ​

1. 📝 题目描述 ​

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

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x``start，x``end， 且满足 xstart ≤ x ≤ x``end，则该气球会被 引爆。可以射出的弓箭的数量 没有限制。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points，返回引爆所有气球所必须射出的 最小 弓箭数。

示例 1：

txt
输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。

示例 2：

txt
输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。

示例 3：

txt
输入：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

2. 🎯 s.1 - 贪心 ​

c
int cmp(const void* a, const void* b) {
    int ra = (*(int**)a)[1], rb = (*(int**)b)[1];
    return ra < rb ? -1 : ra > rb ? 1 : 0;
}

int findMinArrowShots(int** points, int pointsSize, int* pointsColSize) {
    qsort(points, pointsSize, sizeof(int*), cmp);
    int arrows = 1;
    int end = points[0][1];
    for (int i = 1; i < pointsSize; i++) {
        if (points[i][0] > end) {
            arrows++;
            end = points[i][1];
        }
    }
    return arrows;
}
js
/**
 * @param {number[][]} points
 * @return {number}
 */
var findMinArrowShots = function (points) {
  points.sort((a, b) => a[1] - b[1])
  let arrows = 1
  let end = points[0][1]
  for (let i = 1; i < points.length; i++) {
    if (points[i][0] > end) {
      arrows++
      end = points[i][1]
    }
  }
  return arrows
}
py
class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort(key=lambda x: x[1])
        arrows = 1
        end = points[0][1]
        for i in range(1, len(points)):
            if points[i][0] > end:
                arrows += 1
                end = points[i][1]
        return arrows
  • 时间复杂度：O(nlog⁡n)
  • 空间复杂度：O(log⁡n)（排序开销）

算法思路：

  • 按右端点升序排序
  • 维护当前箭的右边界，若下一个气球左端点超过边界，则需要新箭