算法刷题 Day 35 | ● 860.柠檬水找零 ● 406.根据身高重建队列 ● 452. 用最少数量的箭引爆气球

860.柠檬水找零

本题看上好像挺难，其实挺简单的，大家先尝试自己做一做。

https://programmercarl.com/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.html

Tips：

咋眼一看好像很复杂，分析清楚之后，会发现逻辑其实非常固定。

这道题目可以告诉大家，遇到感觉没有思路的题目，可以静下心来把能遇到的情况分析一下，只要分析到具体情况了，一下子就豁然开朗了。

我的题解：

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

406.根据身高重建队列

本题有点难度，和分发糖果类似，不要两头兼顾，处理好一边再处理另一边。

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

Tips：这道题的思路很巧妙，首先根据身高从高到矮进行排序；身高一样的，再按照位置从前到后进行排序，最后对这个排序好的数组进行遍历，从前到后按照其位置进行插入，这样就保证了后序插入节点也不会影响前面已经插入的节点，最终按照k的规则完成了队列。

我的题解：

class Solution {
public:
    static bool cmp(const vector<int>& a, const 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>> queue;
        for(int i=0;i<people.size(); i++){
            int pos = people[i][1];
            queue.insert(queue.begin() + pos, people[i]);
        }
        return queue;
    }
};

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

本题是一道 重叠区间的题目，好好做一做，因为明天三道题目，都是 重叠区间。

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

Tips：

可以看出首先第一组重叠气球，一定是需要一个箭，气球3，的左边界大于了 第一组重叠气球的最小右边界，所以再需要一支箭来射气球3了。

我的题解：

class Solution {
private:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.size() == 0) return 0;
        sort(points.begin(), points.end(), cmp);

        int result = 1; // points 不为空至少需要一支箭
        for (int i = 1; i < points.size(); i++) {
            if (points[i][0] > points[i - 1][1]) {  // 气球i和气球i-1不挨着，注意这里不是>=
                result++; // 需要一支箭
            }
            else {  // 气球i和气球i-1挨着
                points[i][1] = min(points[i - 1][1], points[i][1]); // 更新重叠气球最小右边界
            }
        }
        return result;
    }
};