860.柠檬水找零

思路：

设立钱箱count(3,0)

分成三种情况：

1. 5元钞票，count[0]++;

2. 10元钞票， 判断count[0]是否有钱返回(count[0]==0)，没有返回false. count[0]--,count[1]++

3. 20元钞票，分情况判断，优先用10块：count[0]>=1 && count[1]>=1。或者：count[0]>=3，否则return false；

最后return true;

看视频后：

局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零。

406.根据身高重建队列

思路：

本题有两个需要处理的参数：身高和排序，需要分别进行处理。先确定身高再确定排序，但是找不到排序固定的判断。

看视频后：

如果按照k来从小到大排序，排完之后，会发现k的排列并不符合条件，身高也不符合条件，两个维度哪一个都没确定下来。

按照身高h来排序呢，身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面。那么只需要按照k为下标重新插入队列就可以了。后序插入节点也不会影响前面已经插入的节点，最终按照k的规则完成了队列。

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

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

for(int i=0;i<people.size();i++)

        {

            int position = people[i][1];

            result.insert(result.begin()+position, people[i]);

        }

注意自定义sort排序：

sort(people.begin(),people.end(),cmp);

cmp一定是static的：

static bool cmp(vector<int> &a, vector<int> &b)

    {

        if(a[0]==b[0])

            return a[1] < b[1];

        return a[0] > b[0];

    }

输出result;

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

思路：

先sort原数组，根据内部数组的[0]进行从小到大的排列。

数组compare为points[0]。用compare记录每次与新数组的交集。如果交集为空compare[1]<points[i][0]，则count加1且compare更新为新数组。最后count++,return count。

局部最优：按顺序找到两个区域的交集，再更新下一个区域。

全局最优：按顺序找到最多区域的交集，再更新下一个区域。

看视频后：

局部最优：当气球出现重叠，一起射，所用弓箭最少。

全局最优：把所有气球射爆所用弓箭最少。

先对数组进行排序，如果数组元素个数等于0则return 0. 如果不为0，则至少一只箭，所以result初始化等于1.

如果气球和前一个气球不挨着，即points[i][0]>points[i-1][1], result++；如果挨着，则缩小右边界找交集，point[i][1]= min(points[i-1][1], points[i][1]);最后返回result。

在原数组上修改则不需要建一个数组进行记录。

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][1],points[i][1]);

            }

        }