首页 > 其他分享 >LeetCode 452. 用最少数量的箭引爆气球

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

时间:2022-11-10 16:25:08浏览次数:41  
标签:return 边界 ballon 记录 452 气球 points LeetCode

贪心

1、先按照所有起球的右边界排序,记录第一个气球的右边界位置,如果后续气球的左边界小于记录中的值那么这个气球就是可以被箭射中的,这种情况不做处理。
2、当出现遍历的时候某一个起球的左边界大于当前记录中的值的时候,那么此时第一个箭就射不中当前的气球了,所以箭的数量++,并且记录中的值等于当前遍历气球的有边界,(箭的下标在保证原本应该被射爆的气球还是被射爆的情况下尽可能的往右取,这个值被右下标最小的气球所限制),
3、还有一种情况是,当出现左下边不满足小于记录值的情况箭的数量就++,那么之后再出现后面的气球满足之前的记录值的情况怎么办,这种情况解释为,能被之前的记录的箭所射爆的气球,也一定能被更新之后的箭所射爆(具体解释看官方题解)

第三种情况的图例

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.empty()){
            return 0;
        }
        sort(points.begin(),points.end(),[](const vector<int>& a,const vector<int>& b){
            return a[1]<b[1];
        });
        int pos = points[0][1];//最小的有边界
        int ans = 1;
        for(const vector<int>& ballon:points){
            if(ballon[0]>pos){
                pos = ballon[1];
                ++ans;
            }
        }
        return ans;
    }
};

标签:return,边界,ballon,记录,452,气球,points,LeetCode
From: https://www.cnblogs.com/poteitoutou/p/16877453.html

相关文章

  • [leetcode每日一题]11.10
    864. 获取所有钥匙的最短路径给定一个二维网格 ​​grid​​ ,其中:'.' 代表一个空房间'#' 代表一堵'@'小写字母代表钥匙大写字母代表锁我们从起点开始出发,一次移动是指......
  • leetcode744
    寻找比目标字母大的最小字母Category Difficulty Likes Dislikesalgorithms Easy(45.91%) 249 -TagsCompanies给你一个排序后的字符列表letters,列表中只包含小写英......
  • leetcode69
    x的平方根Category Difficulty Likes Dislikesalgorithms Easy(39.05%) 878 -TagsCompanies给你一个非负整数x,计算并返回x的算术平方根。由于返回类型是整数......
  • leetcode385
    两个数组间的距离值Category Difficulty Likes Dislikesalgorithms Easy(69.82%) 88 -TagsCompanies给你两个整数数组arr1,arr2和一个整数d,请你返回两个数组之......
  • leetcode852
    山脉数组的峰顶索引Category Difficulty Likes Dislikesalgorithms Easy(71.36%) 313 -TagsCompanies符合下列属性的数组arr称为山脉数组:arr.length>=3存在......
  • leetcode374
    猜数字大小Category Difficulty Likes Dislikesalgorithms Easy(51.88%) 265 -Tagsbinary-searchCompanies猜数字游戏的规则如下:每轮游戏,我都会从1到n随机选择......
  • leetcode704
    二分查找Category Difficulty Likes Dislikesalgorithms Easy(54.59%) 1037 -TagsCompanies给定一个n个元素有序的(升序)整型数组nums和一个目标值target,写一个......
  • LeetCode 题解 394. 字符串解码
    题目描述给定一个经过编码的字符串,返回它解码后的字符串。编码规则为:k[encoded_string],表示其中方括号内部的encoded_string正好重复k次。注意k保证为正整数。......
  • LeetCode刷题记录.Day10
    四数相加II题目链接454.四数相加II-力扣(LeetCode)classSolution{public:intfourSumCount(vector<int>&nums1,vector<int>&nums2,vector<int>&nums3,v......
  • leetcode-693-easy
    BinaryNumberwithAlternatingBitsGivenapositiveinteger,checkwhetherithasalternatingbits:namely,iftwoadjacentbitswillalwayshavedifferentva......