代码随想录算法训练营第三十五天 | 860.柠檬水找零、406.根据身高重建队列、用最少数量的箭引爆气球

860.柠檬水找零

题目链接：860.柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

文章讲解/视频讲解：https://programmercarl.com/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.html

思路

只有在顾客支付10美元或者20美元时需要找零。

支付10美元时，只能用5美元找零；支付20美元时，可以用10美元 + 5美元找零，也可以用5美元 + 5美元 + 5美元找零。

因此在顾客支付5美元、10美元时，策略都是固定的，变化在于顾客支付20美元时，应该选择第一种组合还是第二种。

因为10美元只能用于顾客支付20美元时的找零，而5美元既可以用于顾客支付10美元也可以用于20美元，因此应该尽量采用第一种组合。这里便用到了贪心。

C++实现

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        vector<int> billCounts(3, 0); // 代表商家现在有的钞票，5美元、10美元、20美元
        for(int i = 0;i<bills.size();i++){
            if(bills[i] == 5) billCounts[0]++;
            else if(bills[i] == 10){
                billCounts[1]++;
                if(billCounts[0] < 1) return false;
                billCounts[0]--;
            }
            else{
                billCounts[2]++;
                if(billCounts[1] >= 1){
                    if(billCounts[0] >= 1){
                        billCounts[0]--;
                        billCounts[1]--;
                        continue;
                    }
                }
                if(billCounts[0] < 3) return false;
                billCounts[0] -= 3;
            }
        }
        return true;
    }
};

406.根据身高重建队列

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

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

文章讲解/视频讲解：https://programmercarl.com/0406.%E6%A0%B9%E6%8D%AE%E8%BA%AB%E9%AB%98%E9%87%8D%E5%BB%BA%E9%98%9F%E5%88%97.html

思路

没想出来，看了卡哥的教程，可以从h和k这两个维度分别处理。

首先将数组按照身高大小，从大到小排序。排完序后，根据k的值决定对每个元素插入处理。

由于数组已经按身高从大到小排序，而k表示的是前面正好有k个身高大于当前这个人的人。因此把后面的人插到前面，并不会影响前面的人的k值。所以我们可以用贪心的方式来解决。在遍历每一个人时，将这个人插入到当前的第k个位置即可，因为此时前面k个人的身高一定大于等于当前这个人的身高。遍历结束，处理也结束。

又采用链表的方式实现了一遍。

C++实现

// 原来的写法
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        auto cmp = [](vector<int> a, vector<int> b){return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];};
        sort(people.begin(), people.end(), cmp);
        for(int i = 0;i<people.size();i++){
            if(people[i][1] == i) continue;
            int targeti = people[i][1];
            vector<int> tmp = people[i];
            for(int j = i;j>targeti;j--){
                people[j] = people[j - 1];
            }
            people[targeti] = tmp;
        }

        return people;
    }
};
// 链表的实现方式
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        auto cmp = [](vector<int> a, vector<int> b){return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];};
        sort(people.begin(), people.end(), cmp);
        list<vector<int>> que;

        for(int i = 0;i<people.size();i++){
            int position = people[i][1];
            auto it = que.begin();
            while(position--){
                it++;
            }
            que.insert(it, people[i]);
        }

        return vector<vector<int>>(que.begin(), que.end());
    }
};

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

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

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x``start，x``end， 且满足 xstart ≤ x ≤ x``end，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

文章讲解/视频讲解：https://programmercarl.com/0452.%E7%94%A8%E6%9C%80%E5%B0%91%E6%95%B0%E9%87%8F%E7%9A%84%E7%AE%AD%E5%BC%95%E7%88%86%E6%B0%94%E7%90%83.html

思路

首先，我们需要找到重叠区间。为了达成这个目的，首先对points数组排序，以左边界为条件。

然后我们开始找重叠的区间，对于当前的重叠区间curBounds，如果第i个气球的x_start小于等于curBounds的x_end，我们便把这个气球纳入当前的重叠区间，并更新重叠区间curBounds。如果第i个气球不在当前重叠区间中，则另开一个重叠区间，继续判断。

C++实现

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        auto cmp = [](vector<int> a, vector<int> b){return a[0] == b[0] ? a[1] < b[1] : a[0] < b[0];};
        sort(points.begin(), points.end(), cmp);
        int count = 1;
        vector<int> curBounds = points[0];
        for(int i = 1;i<points.size();i++){
            if(points[i][0] <= curBounds[1]){
                curBounds[0] = max(curBounds[0], points[i][0]);
                curBounds[1] = min(curBounds[1], points[i][1]);
            }
            else{
                curBounds = points[i];
                count++;
            }
        }
        return count;
    }
};