leetcode452.用最少数量的箭引爆气球

univerexplorer2025-01-202025-01-20

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

中等（区间选点问题）

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

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

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

示例 1：

输入： points = [[10,16],[2,8],[1,6],[7,12]]
输出： 2
解释： 气球可以用2支箭来爆破:

在x = 6处射出箭，击破气球[2,8]和[1,6]。

在x = 11处发射箭，击破气球[10,16]和[7,12]。

示例 2：

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

示例 3：

输入： points = [[1,2],[2,3],[3,4],[4,5]]
输出： 2
解释： 气球可以用2支箭来爆破:

在x = 2处发射箭，击破气球[1,2]和[2,3]。

在x = 4处射出箭，击破气球[3,4]和[4,5]。

代码一：保留重叠区间

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points = sorted(points,key=lambda x:x[0])
        ans = 0
        def func1(lst):
            nonlocal ans
            if not lst:
                return
            n = len(lst)
            if n == 1:
                ans += 1
                return
            a,b = lst[0]
            start = 1
            while start < n:
                # 如果区间有重叠，说明可以只用一支箭
                m,l = lst[start]
                if m <= b:
                    a = max(a,m)
                    b = min(b,l)
                    start += 1
                    continue
                break
            ans += 1
            func1(lst[start:])
        func1(points)
        return ans

思路：

从左到右寻找公共重叠的区间，只要在区间内射一支箭就可以将这些气球引爆。剩下的区间依次重复。

代码二：代码一优化

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points = sorted(points,key=lambda x:x[0])
        ans = 1
        a,b = points[0]
        for i,j in points[1:]:
            if i <= b:
                a = max(a,i)
                b = min(b,j)
                continue
            ans += 1
            a,b = i,j
        return ans

思路：

代码二方法与代码一大体思路差不多，只是不需要修改数组，遍历数组即可。

代码三：区间选择右端点

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points = sorted(points,key=lambda x:(x[0],x[1]))
        ans = 1
        num = points[0][1]
        for a,b in points[1:]:
            if num < a:
                ans += 1
                num = b
                continue
            num = min(num,b)
        return ans

思路：

代码三进一步优化，不需要保留区间的两个端点，只要右端点即可。

代码四：按右端点排序（最终优化）

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points = sorted(points,key=lambda x:x[1])
        ans = 1
        num = points[0][1]
        for a,b in points[1:]:
            if num < a:
                ans += 1
                num = b
        return ans