代码随想录训练营Day26:贪心算法：04

1.860柠檬水找零

贪心策略：先找大钱，再找小钱，20的不参与找钱

思路：用five,ten存放5元和10元的个数，初始化都是0，如果给的钱是5元，直接five++,如果给的是10元，只能找5，判断此时有没有5，有就找，没有就返回false,如果给的钱是20，分三种情况，1：有10元先找十元再找5元。2.没有10元，找三个5元。3.如果5元，10元都不够，返回false.

class Solution {
public:
    //贪心算法先找大钱，再找小钱
    bool lemonadeChange(vector<int>& bills) {
        int five = 0,ten = 0;//代表两种的个数，因为20是就算你有也不能参与找零
        int n = bills.size();
        for(int i = 0;i<n;i++){
            if(bills[i] == 5){
                five++;
            }else if(bills[i] == 10){
                if(five==0){
                    return false;
                }else{
                    five--;
                }
                ten++;
            }else if(bills[i] == 20){
                if(ten>0){
                    ten--;
                    if(five>0){
                        five--;
                    }else{
                        return false;
                    }
                }else{
                    if(five>=3){
                        five = five - 3;
                    }else{
                        return false;
                    }
                }
            }
        }
        return true;
    }
};

2.406根据身高重建队列

贪心策略：分为两次贪心。

第一次贪心：第一次贪心按照身高从高到低进行排列（如果同样的身高，那么个数小的在前面）

第二次贪心：遍历，按照个数的大小进行插入（由于前面的遍历保证了你前面的数一定是比你大的数，所以你只需要找到第i个位置插入即可）。

重点：比较器的设计

附加知识点：vector的扩容花费的时间比较长。所以另外一种方法使用list来做，相对来说花费时间比较少。

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) {
        sort(people.begin(),people.end(),cmp);
        vector<vector<int>> result;
        for(int i = 0;i<people.size();i++){
            int position = people[i][1];
            result.insert(result.begin()+position,people[i]);
        }
        return result;
    }
};

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

贪心策略：【left，right】一个right能够覆盖更多的left。

思路：按照先left，再right的方式进行升序排列，然后直到遇到了一个position[i][0]>right此时计数+1的同时更新[left,right].

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];
    }
    //思路：先进行排序，然后按照顺序遍历，找到第i个位置能射的最多的个数
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(),points.end(),cmp);
        int n = points.size();
        if(n == 0)return 0;
        int left = points[0][0];
        int right = points[0][1];
        int val = 1;
        for(int i = 0;i<n;i++){
            left = points[i][0];//由于这个是递增的，所以这个就是左边的最大值
            right = min(right,points[i][1]);//代表这一块的右边的最小值
            if(left>right){//代表超过了，此时对应的射箭次数就要+1
                val++;
                right = points[i][1];//此时要更新右边的位置
            }
        }
        return val;
    }
};