第三十七天 | 860.柠檬水找零 406.根据身高重建队列 452.用最少数量的箭引爆气球

题目：860.柠檬水找零（很像模拟题）

看来贪心题目基本都需要看题解了，哎。

甚至有想不通的地方，都说不出哪里不通

看了题解怎么这么简单？完全就是模拟了收入和找零的这个过程。看来懵的很重要一点就是不知道咋去表示这个动态过程。

其实你定义三个变量就好了呀，分别代表手上剩余的5，10，20面额纸币的张数，然后用for循环依次遍历bills，对三个变量进行运算，就可以模拟一次交易。当手上某一种纸币的数量不够找了，就false了。

这道题原来可以ac的如此直白。

代码如下

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

回顾一下局部最优：对于20元找零优先用10元（因为5更万能，留在手上），每次都能找开。

全局最优：能给每位顾客正确找零

题目：406.根据身高重建队列（两边分开考虑）（代码值得好好琢磨）

思路：

        有h和k两个维度需要考虑，要先确定一个维度后再确定另外一个维度。

有了这个提示，尝试一下：

        先将所有数据的身高（h）从大到小排序，使身高这个维度达到有序，然后再考虑前面有几个人的身高大于或者等于他。

        排序得到的结果：对于任意一个数据，它左边都是大于他的，右边都是小于他的。所以每一个元素前插，不会影响其他元素的 j 值，那就大胆前插，他的 j 是几就给他插到满意的位置。

        理论成立。自己琢磨的七七八八了。

局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性

全局最优：最后都做完插入操作，整个队列满足题目队列属性

用代码咋实现呢？怎样改变二维数组中元素的顺序呢？

        1.通过cmd指令，在sort函数中指定按照身高从大到小排

        2.通过insert()库函数，在二维数组中插入（注意传参传什么）

        3.vector的内部扩容原理

        4.排序中的cmp是什么

代码如下：

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>> que;
        for(int i = 0; i < people.size(); i++) {
            int pos = people[i][1];        //确定插入位置
            que.insert(que.begin() + pos, people[i]);
        }
        return que;
    }
};

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

这道题贪心的思路很直观，重复的气球一起射，但是具体代码怎么实现？怎么模拟真实情况？

代码实现：

        1.进行排序（又需要cmp，使其按照第一个数进行排序）：统一按照左边界进行排序，按照左边界排序之后，重叠的气球就尽量相邻了

        2.判断气球是否重复：如果第 i 个气球的左边界大于第 i - 1 个气球的右边界，那么此时两个气球不重叠，那么一定要增加一个弓箭。 

        3.如果points[i][0] > points[i - 1][1]了，如何判断能不能再多带一个气球一起射爆呢？需要更新右边界。（这一点太巧妙了，神）

代码如下：

自己的一点理解：

        初始时result = 1的这只箭用来我们认为他必定用来射爆第一个气球，至于第二个气球能不能一起射爆，取决于for循环遍历到第二个气球时。if判断为真那么就不需要多用一只箭，反之则需要。若第二个气球能一起射爆，在第二次for循环中需要更新第二个气球的右边界。

        同理：第三个气球能不能也用这只箭射爆，取决于for循环遍历到三时的if判断。

        我想表达的意思就是说，每多添加一只箭，他的作用是用来射本轮for循环（即if判断为真的那一轮for循环）的那个气球（假定称为A）；至于其他气球能不能顺带射中，那是要在其他轮次的for循环中的判断，如果能一起射中（即在其他轮次中if判断为否），不过是改变这只箭射A时x坐标的大小罢了。

        这样理解一下做题更顺。

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) {
        int result = 1;       //points不为空至少需要一只箭
        sort(points.begin(), points.end(), cmp);
        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;
    }
};