1. 贪心算法
感谢代码随想录
贪心算法——由局部最优推导出全局最优
1.1. 饼干分配
按照常识推导，但所用知识需要逻辑正确
大胃口 吃 大饼干，如果胃口大了，可以换小胃口 大饼干不能喂小胃口，如果饼干小了， 不能喂更小的饼干
小饼干去喂小胃口，如果饼干小了，换大饼干 小胃口不能吃小饼干，胃口大了，不能换大胃口
1.2. 贪心
- 有变化： pre< 0 & cur > 0 或 pre> 0 & cur< 0
- 平台,只记录最右边，pre<=0 & cur>0
平台上升， 平台期仍保持原有状态
1.3. 最大连续和
当连续和 < 0 时，后续增加会减小数值，应从当前位置继续开始
注意： count计算后便与result比较，而不是先归零
1.4. 买卖股票的最佳时机
总利润 = 每一条的利润
贪心：每次贪正利润
1.5. 跳跃游戏
从i 能够到达x = 从i的跳跃范围能够到达x，且i只能在跳跃范围内移动
1.6. 跳跃游戏2
x 是第i-1次跳跃位置， cover(i-1)
如果i大于了cover(i-1)，则需要选择cover(i-1)中能跳跃的最大位置作为新一跳的界限，并增加一步
1.7. k次取反最大数组和
- 选择将负数反转
- 选择最小的绝对值进行反转
或者每次选择最小值，反转，但是更复杂
1.8. 加油站
- 首先排除不能循环的情况；
- 一定能够循环
- 从0开始的区间为负值情况，则起点错误，从下一个起点开始，直到找到能够值不为负的区间
同时，从后向前相加，如果能加从0开始的最小和，相加为正数时，则为开始起点
1.9. 糖果分发
分发糖果：要求分高的同学的糖果一定比两边分低的同学糖果数量多
注意贪心比较的方向， 所有的结果都能比较得到
- 依次比较左右孩子，
- 依次比较左孩子，从左向右遍历， 可以使用到上一次比较的结果
- 依次比较右孩子，从右向左遍历， 遍历时，选择max(本轮比右孩子多的糖果，从左边得到的糖果)
1.10. 柠檬水找零
优先将面额较大的零钱找出，因为小零钱更加万能
1.11. 根据身高重建序列
讨论两个维度 ，首先固定一个维度，再讨论下一个维度
- 按照身高从大到小排序，以此作为插入顺序，同时需要规定k值小的排在前面
- 高身高的优先插入后，后面小身高的插入不会影响k值
vector 与 list插入的区别， vector插入时涉及底层扩容，比list插入效率低
vector<int> v;
list<int> l;
v.insert(v.begin()+pos, val); // 可以直接使用pos插入
auto it = l.begin();
it = next(it, pos);
l.insert(it, val); // 必须使用迭代器指定位置
1.12. 射击气球
贪心算法，一定要举出贪心的例子，来验证算法，
首先需要排序，根据排序顺序选择判断结果
- 将右边界排序，记录最左边右端节点，但有其他值超过节点时，需射出一箭
将左边界排序，记录最右端节点，如果其他值查过节点时，需要射出一箭
1.13. 无重叠区间
使用右边界，每一个不相交的区间是保留下的区间，其余都需删除
左排序时，统计有重复区域的区间，然后删除
1.14. 划分字母区间
当区间[a,b]之间字符的最大值以达到时，这个区间为字母区间，并将a置为新的区间开始b+1
1.15. 合并区间
合并区间，从左向右比较，只能使用左排序
1.16. 最小单调递增数字
如果有n1 n2 n3情况，
如果n2 > n3， 则其最大的递增序列为(n2-1) 9
如果n1 > n2， 最大为(n1-1) 9 9
如果序列比较n-1与n，则for循环最小值为1
1.17. 监控二叉树
优先从叶子节点开始监控，因为叶子节点监控数量为指数级
有三种节点状态
- 无监控
- 有监控
- 有摄像头
对叶子节点进行监控，则空节点需设置为有监控状态
状态返回
- left 与right 都是监控状态，则mid需返回无监控1
- left，right有一个是无监控1， 则mid需设置有摄像头3，并增加一个摄像头
- left, right有一个有摄像头，则mid返回有监控2
1.18. 友军数量
贪心思想： 前面杀死后面的所有参议员
使用flag 标识，前方时候有敌军
- 前方有敌军，自身被杀死
- 但是多了一个友军,flag+1
- 前方没有敌军，自身还活着，友军数量+1
