day35 柠檬水找零 根据身高重建队列 用最少数量的箭引爆气球

题目1：860 柠檬水找零

题目链接：860 柠檬水找零

题意

一杯柠檬水5美元，每位顾客只买一杯柠檬水，支付5美玉，10美元，20美元，必须正确找零

开始时并没有零钱 若可以正确找零，则返回true，反之返回false

贪心策略

尽可能保留5美元的零钱，5更万能（既能对10找零，又能对20找零） 优先使用10进行找零

代码

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        if(bills[0]!=5) return false;
        int nums5 = 0;
        int nums10 = 0;
        int nums20 = 0;
        for(int i=0;i<bills.size();i++){
            if(bills[i]==5) nums5 += 5;
            if(bills[i]==10){
                if(nums5!=0){
                    nums5 -= 5;
                    nums10 += 10;
                }
                else return false;
            }
            if(bills[i]==20){
                if(nums10!=0 && nums5!=0){
                    nums10 -= 10;
                    nums5 -= 5;
                }
                else if(nums5>=15){
                    nums5 -= 15;
                }
                else return false;
            }
        }
        return true;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(1)

题目2：406 根据身高重建队列

题目链接：406 根据身高重建队列

题意

people[i]=[hi，ki]   表示第i个人的身高是hi，前面有ki个身高大于等于hi的人，按正确顺序重组队列

贪心策略

先确定一个维度，先比较h的维度，按照h从大到小排序，然后再比较k的维度 按照k从小到大往前插入

数组

代码

class Solution {
public:
    static bool cmp(vector<int>& a,vector<int>& b){
        if(a[0]==b[0]) return a[1]<b[1];//升序排序
        return a[0]>b[0];//降序排序
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        vector<vector<int>> queue;
        //身高按照降序排序，从大到小排序
        sort(people.begin(),people.end(),cmp);
        //根据k插入到队列前面  注意是插入到队列哦，不是people
        for(int i=0;i<people.size();i++) queue.insert(queue.begin()+people[i][1],people[i]);
        return queue;
    }
};

• 时间复杂度：O(nlog n + n^2)
• 空间复杂度：O(n)

！！！注意！！！

使用vector是非常费时的，C++中vector（可以理解是一个动态数组，底层是普通数组实现的）如果插入元素大于预先普通数组大小，vector底部会有一个扩容的操作，即申请两倍于原先普通数组的大小，然后把数据拷贝到另一个更大的数组上。

所以使用vector（动态数组）来insert，是费时的，插入再拷贝的话，单纯一个插入的操作就是O(n^2)了，甚至可能拷贝好几次，就不止O(n^2)了。

链表

class Solution {
public:
    static bool cmp(vector<int>& a,vector<int>& b){
        if(a[0]==b[0]) return a[1]<b[1];//升序排序
        return a[0]>b[0];//降序排序
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        list<vector<int>> que;
        //身高按照降序排序，从大到小排序
        sort(people.begin(),people.end(),cmp);
        //根据k插入到队列前面  注意是插入到队列哦，不是people
        for(int i=0;i<people.size();i++){
            int position = people[i][1];
            std::list<vector<int>>::iterator it=que.begin();
            while(position--){
                it++;
            }
            que.insert(it,people[i]);
        }
        return vector<vector<int>>(que.begin(),que.end());
    }
};

• 时间复杂度：O(nlog n + n^2)
• 空间复杂度：O(n)

题目3：452 用最少数量的箭引爆气球

题目链接：452 用最少数量的箭引爆气球

题意

points[i]=[xstart，xend]表示水平直径在xstart和xend之间的气球，y坐标未知

一支箭可以从垂直x轴的任意位置x处射出一直前进，若xstart<=x<=xend，气球会被引爆，求最小弓箭数

贪心策略

重叠区间的气球用1个箭射中，箭的数量最少

代码

class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b){
        //左边界升序
        return a[0]<b[0];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        //对数组的左边界升序排序
        sort(points.begin(),points.end(),cmp);
        //收集弓箭数
        int result = 1;
        for(int i=1;i<points.size();i++){
            //两气球不重叠
            if(points[i][0]>points[i-1][1]) result++;
            //两气球重叠
            else{
                //判断第三个气球，更新右边界
                points[i][1] = min(points[i][1],points[i-1][1]);
            }
        }
        return result;
    }
};

• 时间复杂度：O(nlog n)，因为有一个快排
• 空间复杂度：O(1)，有一个快排，最差情况(倒序)时，需要n次递归调用。因此确实需要O(n)的栈空间