[1006]贪心刷题思路
贪心
本篇博客只记录刷题思路不记录具体代码，用于本人快速回顾
题目来源代码随想录
刷完感想：连刷三个小时头都要晕了，去吃牛肉饭了🤤
:::tip 和贪心题相关的提示
局部最优得到全局最优
:::
分发饼干
非常标准的贪心
先满足胃口小的，注意这种情况是for饼干if胃口，因为无论是否满足，饼干一定会后移动，胃口不一定会后移（和先满足胃口的思路不一样，这种是胃口一定会前移，饼干不一定前移）
第二tips就是用if优化for循环，做一个自减
摆动序列
笑死感觉不算贪心算模拟，思路上有难度
比较[当前差值]和[上一个差值]
相同不算，不同算一个
最大子序和
贪心的点在于：碰到连续和为负数的情况就舍弃，不要影响后续的最大和
买股票的最佳时间Ⅱ
非常简单：求差，正数就算上利益
（不用担心连续正数，这种情况也考虑到了）
跳跃游戏
思路：不能从后往前，因为除了要判断能否往后到达，还要考虑前面能不能到这里
==》考虑最远范围 + 能不能到达（从前考虑就比较容易，刚好是之前的最大值）
跳跃游戏Ⅱ
比较有难度，难度在于找到更新maxReach的时机，是到了当前跳跃边界才更新cnt，而不是更新了maxReach就更新cnt
k次取反求最大值
思路easy，从小到大排序
一次贪心：先把最小的负数更新成正数
二次贪心：如果还有次数，偶直接抵消，奇就找到最小的正数为负
加油站
初步思路想到了根据gas和cost的差判断找起始点
但是以为找到最大值就行了
nono，应该用前缀和找到负数和的下一个
而且有个证明：有解就是唯一解
还需要判断一下sum<0的话无解
分发糖果
[老师怎么是hard，我是废物先溜了]
柠檬水找零
easy，更新5r、10r的张数能否满足就行
贪心的点在于20可以换3*5，也可以10+5，这个时候应该有限10+5
but第一反应怎么是用数组存？肯定是int存啊，奇怪脑子
身高重建队列
太妙了
初步思路想到了先根据身高排列，再根据人数调整位置
但是应该从大到小排（妙!!!!!），然后直接插入到对应的位置
而且注意用LinkedList的add(index,value)方法更快，后续再toArray(new int[size][])
最少数量箭引爆气球
服了没读懂题目
思路就是找排序 + 是否交集（前一个气球的末值和后一个气球的初值）
没有交集多加一支箭
有交集就更新后一个气球的末值为前后气球末值的最小值，不用加箭