企业官网建设流程全解析

题目

标题和出处

标题：用最少数量的箭引爆气球

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

难度

6 级

题目描述

要求

有一些球形气球贴在一堵用二维平面表示的墙面上。墙面上的气球使用二维整数数组points \texttt{points}points表示，其中points[i] = [x start , x end ] \texttt{points[i] = [x}_\texttt{start}\texttt{, x}_\texttt{end}\texttt{]}points[i] = [xstart​, xend​]表示水平直径在x start \texttt{x}_\texttt{start}xstart​和x end \texttt{x}_\texttt{end}xend​之间的气球。不知道气球的确切y \texttt{y}y坐标。

一支箭可以在x \texttt{x}x轴上的不同点完全垂直地射出。在坐标x \texttt{x}x处射出一支箭，若有一个气球的直径的开始和结束坐标为x start \texttt{x}_\texttt{start}xstart​和x end \texttt{x}_\texttt{end}xend​，且满足x start ≤ x ≤ x end \texttt{x}_\texttt{start} \le \texttt{x} \le \texttt{x}_\texttt{end}xstart​≤x≤xend​，则该气球会被引爆。可以射出的箭的数量没有限制。射出的箭将无限地前进并引爆经过的气球。

给定数组points \texttt{points}points，返回引爆所有气球所必须射出的最小箭数。

示例

示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]] \texttt{points = [[10,16],[2,8],[1,6],[7,12]]}points = [[10,16],[2,8],[1,6],[7,12]]
输出：2 \texttt{2}2
解释：气球可以用2 \texttt{2}2支箭引爆：

• 在x = 6 \texttt{x = 6}x = 6处射出箭，击破气球[2,8] \texttt{[2,8]}[2,8]和[1,6] \texttt{[1,6]}[1,6]。
• 在x = 11 \texttt{x = 11}x = 11处发射箭，击破气球[10,16] \texttt{[10,16]}[10,16]和[7,12] \texttt{[7,12]}[7,12]。

示例 2：

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

示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]] \texttt{points = [[1,2],[2,3],[3,4],[4,5]]}points = [[1,2],[2,3],[3,4],[4,5]]
输出：2 \texttt{2}2
解释：气球可以用2 \texttt{2}2支箭引爆：

• 在x = 2 \texttt{x = 2}x = 2处发射箭，击破气球[1,2] \texttt{[1,2]}[1,2]和[2,3] \texttt{[2,3]}[2,3]。
• 在x = 4 \texttt{x = 4}x = 4处射出箭，击破气球[3,4] \texttt{[3,4]}[3,4]和[4,5] \texttt{[4,5]}[4,5]。

数据范围

• 1 ≤ points.length ≤ 10 5 \texttt{1} \le \texttt{points.length} \le \texttt{10}^\texttt{5}1≤points.length≤105
• points[i].length = 2 \texttt{points[i].length} = \texttt{2}points[i].length=2
• -2 31 ≤ x start < x end ≤ 2 31 − 1 \texttt{-2}^\texttt{31} \le \texttt{x}_\texttt{start} < \texttt{x}_\texttt{end} \le \texttt{2}^\texttt{31} - \texttt{1}-231≤xstart​<xend​≤231−1

解法

思路和算法

根据贪心思想，为了在引爆所有气球的条件下将射出的箭数最小化，应确保每个气球都至少被一支箭经过，且每只箭经过的气球数最大化。

考虑结束坐标最小的气球，称为A \text{A}A气球，将该气球的坐标范围记为[ start A , end A ] [\textit{start}_\text{A}, \textit{end}_\text{A}][startA​,endA​]，则为了将A \text{A}A气球引爆，必须有一支箭在A \text{A}A气球的坐标范围中射出。为了将射出的箭数最小化，应考虑在该坐标范围中射出的一支箭可以经过的最多气球数。

如果有另一个气球，称为B \text{B}B气球，其坐标范围是[ start B , end B ] [\textit{start}_\text{B}, \textit{end}_\text{B}][startB​,endB​]，则由于end A \textit{end}_\text{A}endA​是最小的结束坐标，因此必有end A ≤ end B \textit{end}_\text{A} \le \textit{end}_\text{B}endA​≤endB​。考虑以下三种情况。

• 如果start B > end A \textit{start}_\text{B} > \textit{end}_\text{A}startB​>endA​，则引爆A \text{A}A气球的箭一定不能引爆B \text{B}B气球，因此在坐标范围[ start A , end A ] [\textit{start}_\text{A}, \textit{end}_\text{A}][startA​,endA​]中的任意坐标射出箭都只能引爆A \text{A}A气球，不能引爆B \text{B}B气球。

• 如果start B ≤ start A \textit{start}_\text{B} \le \textit{start}_\text{A}startB​≤startA​，则引爆A \text{A}A气球的箭一定能引爆B \text{B}B气球，因此在坐标范围[ start A , end A ] [\textit{start}_\text{A}, \textit{end}_\text{A}][startA​,endA​]中的任意坐标射出箭都能引爆A \text{A}A气球和B \text{B}B气球。

• 如果start A < start B ≤ end A \textit{start}_\text{A} < \textit{start}_\text{B} \le \textit{end}_\text{A}startA​<startB​≤endA​，则在坐标范围[ start B , end A ] [\textit{start}_\text{B}, \textit{end}_\text{A}][startB​,endA​]中的任意坐标射出箭能引爆A \text{A}A气球和B \text{B}B气球。

三种情况都满足在坐标end A \textit{end}_\text{A}endA​处射出箭可以使引爆的气球数最大化。

由此可以得出贪心策略：每次在尚未引爆的气球中选择结束坐标最小的气球，从该气球的结束坐标处射出箭，可以用最少数量的箭引爆所有气球。

具体做法是，将数组points \textit{points}points按结束坐标升序排序，用arrow \textit{arrow}arrow表示射出的箭的坐标，将第一支箭的坐标设为arrow = points [ 0 ] [ 1 ] \textit{arrow} = \textit{points}[0][1]arrow=points[0][1]，则第一支箭可以引爆结束坐标最小的气球。从下标1 11开始遍历排序后的数组points \textit{points}points，当遍历到下标i ii时，执行如下操作。

• 如果points [ i ] [ 0 ] ≤ arrow \textit{points}[i][0] \le \textit{arrow}points[i][0]≤arrow，则第i ii个气球的开始坐标小于等于arrow \textit{arrow}arrow且结束坐标大于等于arrow \textit{arrow}arrow，因此从坐标arrow \textit{arrow}arrow处射出的箭可以引爆第i ii个气球，不更新射出的箭的坐标和射出的箭的数量。

• 如果points [ i ] [ 0 ] > arrow \textit{points}[i][0] > \textit{arrow}points[i][0]>arrow，则第i ii个气球的开始坐标大于arrow \textit{arrow}arrow，因此从坐标arrow \textit{arrow}arrow处射出的箭不能引爆第i ii个气球，为了引爆第i ii个气球且将射出的箭数最小化，应在坐标points [ i ] [ 1 ] \textit{points}[i][1]points[i][1]处射出箭，因此将arrow \textit{arrow}arrow更新为points [ i ] [ 1 ] \textit{points}[i][1]points[i][1]，将射出的箭的数量加1 11。

遍历结束之后，即可得到引爆所有气球的最小箭数。

贪心策略的正确性说明如下。

1. 每次射出箭时，都是在尚未引爆的气球中选择结束坐标最小的气球，从该气球的结束坐标处射出箭，该做法可以确保结束坐标最小的气球被引爆，且可以被引爆的气球数最大化。

2. 只有当已经射出的箭无法引爆更多的气球时，才射出新的箭，因此每次射出的箭都必不可少，如果减少射出的箭数则一定不能引爆所有气球。

代码

classSolution{publicintfindMinArrowShots(int[][]points){Arrays.sort(points,(a,b)->{if(a[1]==b[1]){return0;}else{returna[1]>b[1]?1:-1;}});intcount=1;intarrow=points[0][1];intlength=points.length;for(inti=1;i<length;i++){int[]point=points[i];if(point[0]>arrow){arrow=point[1];count++;}}returncount;}}

复杂度分析

• 时间复杂度：O ( n log ⁡ n ) O(n \log n)O(nlogn)，其中n nn是数组points \textit{points}points的长度。排序需要O ( n log ⁡ n ) O(n \log n)O(nlogn)的时间，排序之后遍历数组需要O ( n ) O(n)O(n)的时间，因此时间复杂度是O ( n log ⁡ n ) O(n \log n)O(nlogn)。

• 空间复杂度：O ( n ) O(n)O(n)，其中n nn是数组points \textit{points}points的长度。由于待排序数组的元素是数组，因此排序需要O ( n ) O(n)O(n)的空间。