本文最后更新于607 天前,其中的信息可能已经过时,如有错误请发送邮件到tomding1065@gmail.com
1.本题思路挺好理解的,但是我是真的想不到每次去更新本次递归的右节点来判断i - 1 和i和i + 1是否也能够用一支箭引爆,本题的逻辑为当前一个节点的右节点小于当前节点的左节点的时候箭矢自动+ 1,要是else即更新当前节点的右节点为前一个节点和当前节点的最小值,用于在下一次循环里判断他们与当前节点的下一个节点是否有重合部分,这样就可以通过循环一直向下遍历下去。
CPP
class Solution {
static bool cmp(vector<int>& a, vector<int>& b){
return a[0]<b[0];
}
public:
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(), points.end(), cmp);
int res = 1;
if(points.size() == 0)return 0;
for(int i = 1; i < points.size(); i++){
if(points[i][0] > points[i - 1][1]){
res++;
}else{
points[i][1] = min(points[i][1], points[i - 1][1]);
}
}
return res;
}
};