贪心
解题思路
为了让气球尽可能的重叠，需要按照气球起始位置对数组进行排序，如果从左向右遍历气球数组，则要靠左尽可能让气球重复；
如下图所示：第一个气球和第二个气球重合，即
points[1][0] < points[0][1]，所以不需要一支箭，否则需要增加一支箭；第三个气球是否和第二个重合、是否和第一个重合呢？
- 判断与第二个气球是否重合，可根据
points[i][0] < points[i-1][1]判断，即 当前气球的左边界 小于 上一个气球的右边界；- 判断与第一个气球是否重合，可根据
points[i][0] < points[i-2][1]判断，即 当前气球的左边界 小于 上上一个气球的右边界；- 第三个气球和第二个气球是否重叠，第三个气球都需要增加一支箭，那如果前三个都气球重叠就不需要增加一只箭了；所以可以将 第一个和第二个气球的右边界 比较后取最小值，并更新到 第二个气球的右边界；可以将 对比前两个气球 转化成 对比前一个气球 这个简单问题；
图解
复杂度
-
时间复杂度：
O(nlogn)，其中 n 是数组 points 的长度，排序的时间复杂度为O(nlogn)，对所有气球进行遍历的时间复杂度为O(n)； -
空间复杂度：
O(logn)，即为排序需要使用的栈空间；
代码实现
var findMinArrowShots = function (points) {
let arrows = 1; // 初始化箭头数量
// 1. 对气球的起始位置进行排序
points.sort((a, b) => a[0] - b[0]);
// 2. 对比气球在 x 轴方向是否有重叠
for (let i = 1; i < points.length; i++) {
if (points[i][0] > points[i - 1][1]) {
// 2-1. 与上一个气球没有重叠
arrows++;
} else {
// 2-2. 与上一个气球重叠，并更新当前气球的右边界（更新右边界的原因：有可能存在 2 个以上的气球重叠）
points[i][1] = Math.min(points[i - 1][1], points[i][1]);
}
}
return arrows;
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 406. 根据身高重建队列
上一篇
评论
