力扣刷题记录（13）LeetCode：406、452、435

目录

406.根据身高重建队列

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

435.无重叠区间?

406.根据身高重建队列

?

题目说有一个people数组，people的元素也是一个数组，里面包含h和k，h表示人的身高，k表示前面有k个人的身高高于自己。现在要就你根据h、k这两个维度对people进行重新排序。和上一篇文章的135.分发糖果问题一样，要同时考虑两个维度。分发糖果是一个维度一个维度地去解决的，正反两次遍历。这道题也一样，先按身高从大到小排序，再确定每个人前面比他高的人的人数。

class Solution {
public:
    bool static cmd(const vector<int>& a,const vector<int>& b)
    {
        if(a[0]==b[0])   return a[1]<b[1];
        else    return a[0]>b[0];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(),people.end(),cmd);
        vector<vector<int>> ans;
        for(int i=0;i<people.size();i++)
        {
            int positon=people[i][1];
            ans.insert(ans.begin()+positon,people[i]);
        }
        return ans;
    }
};

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

?

思路就是每一箭都尽可能的多引爆气球，那如何才能多引爆呢？需要在不漏掉气球的情况下，尽可能多地引爆重叠的气球。可以根据气球的左值对所有的气球进行排序，这样可以使相邻的两个气球在vector中也是相邻的。?我们需要设置一个整型变量lim，用来记录一组气球中的最小右边界值，这样可以保证在不漏掉气球的情况下去引爆尽可能多的气球。

class Solution {
public:
    static bool cmp(const vector<int>& a,const vector<int>& b)
    {
        return a[0]<b[0];
    }
    
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.size()==1)    return 1;
        sort(points.begin(),points.end(),cmp);
        int ans=1,lim=points[0][1];
        for(int i=1;i<points.size();i++)
        {
            //判断是否需要增加一支箭
            if(points[i][0]>lim)
            {
                ans++;
                //新增加一支箭就需要重新定义最小右边界
                lim=points[i][1];
            }
            else
            {
                //更新最小右边界
                lim=min(lim,points[i][1]);
            }
        }
        return ans;
    }
};

435.无重叠区间?

?

我们可以先对区间集合按照左值进行排序，使左值相邻的两个集合在区间集合中也是相邻的。然后遍历区间集合，如何当前集合与上一个集合重叠，那就必须移除一个集合。那问题来了，是移除当前区间还是移除上一个区间呢？这就需要比较两个区间的右边界值了，我们肯定是移除右边界大的那个，因为右边界越大区间所覆盖的范围就越大，覆盖范围越大就意味着我们肯需要移除更多的集合。所以当遇到两个区间重叠时，我们要移除右边界大的，保留右边界小的。

class Solution {
public:
    static bool cmp(const vector<int>& a,const vector<int>& b)
    {
        if(a[0]==b[0]) return a[1]<b[1];
        else    return a[0]<b[0];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.size()==1) return 0;
        sort(intervals.begin(),intervals.end(),cmp);
        //ans记录移除区间次数，lim记录上一个区间的右边界值
        int ans=0,lim=intervals[0][1];
        for(int i=1;i<intervals.size();i++)
        {
            //判断当前区间是否与上一个区间重合
            if(intervals[i][0]<lim)
            {
                //如果重合了，留下右边界较小的集合
                lim=min(lim,intervals[i][1]);
                ans++;//移除次数加一
            } 
            else
            {
                //未重合就更新右边界值
                lim=intervals[i][1];
            }
        }
        return ans;
    }
};

?