455. 分发饼干
376. 摆动序列
53. 最大子数组和
Note: 53题的贪心做法实际就是动态规划做了一层优化。dp[i] = max(dp[i - 1] + num, num) 优化为sum = max(sum+num, num)，进一步可变为sum = sum < 0 ? num : sum + num 来避免INT最小值溢出。
122. 买卖股票的最佳时机 II
Note: 注意122题，和376都是类似的，要根据数据的山谷和山峰来做，但相比于用while去获取山谷和山峰值，更好的办法是只比较前一个值和后一个值的大小，也符合贪心算法“局部最优”的思想，当然，也可以用动态规划来做！
55. 跳跃游戏
45. 跳跃游戏 II
Note: 注意45题，仍然采用55题的方法，不断更新当前最大覆盖范围，并在可走的当前最大覆盖范围内一步一步走，但需要同时维护一个下一次最大覆盖范围，以便在当前覆盖范围走完时进行更新（这一步内所有可走点的最大覆盖范围，具体哪个点并不关心，只需要次数最少就够了，肯定是越远越好，而且在当前可覆盖范围内一步一步走，避免错过目标点）。修改最远到达距离为n-2可以简化代码，在原本代码中，i到n-1才终止，因此如果当前覆盖范围curCover恰好等于n-1，则最后一次循环会进入覆盖范围更新，造成ans多一次+1，但是实际上并不需要这次+1，所以需要提前终止。因此，将i改为到n-2终止，则即使最后一次循环中ans加了一，也没关系，因为此时curCover等于n-2，还需要走一步才能到终点。这样做省去了特殊情况的考虑（并且n=1也不用单独拎出来处理）

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        int curCover = 0, nextCover = 0;
        for (int i = 0; i < n - 1; ++i) {
            nextCover = max(nums[i] + i, nextCover);
            if (i == curCover) {
                ++ans;
                curCover = nextCover;
            }
        }
        return ans;
    }
};

1005. K 次取反后最大化的数组和
Note: 由于本题数据大小有限制，因此可以用计数排序，省去了sort的O(nlogn)耗时
134. 加油站
Note: 本题先算rest[i] = gas[i] - cost[i]，然后从0开始累加部分和（先累加），然后判断当前部分和sum[0, i]是否≥0，如果不是，那么舍弃之前的部分和，重新开始计算（置部分和为0），否则继续计算部分和。这里隐藏的理由是，如果部分和sum[0, i] < 0，那么任何一点p∈[0, i]都不可能作为行驶起点：假设有一点p可作为行驶起点，那么必有sum[p, i] ≥ 0，由于sum[0, i] < 0，则sum[0, p-1] < 0因此sum[0, p-1]在之前应该被舍弃了，即sum[0, i] = sum[p, i] < 0，与sum[p, i] ≥ 0矛盾。因此最小的起点start应该是i+1，以此方式遍历rest数组，同时维护一个总体和，遍历完成后，先判断总体和是否≥0，若不是，那么根本不可能走完一圈，返回-1，否则返回start。本题和53.最大子数组和思想一致。
135. 分发糖果
Note: 本题不可以同时兼顾两边，因为一个孩子获得的糖果同时被两边孩子获得的糖果影响，无法通过一次遍历处理完毕，因此分两个方向：从前到后遍历处理“后比前高”，从后向前遍历处理“前比后高”，原因在于“评分高的孩子获得的糖果多”，故评分更高的孩子应该后被处理，处理“后比前高”时，后面的孩子评分更高，应该从前到后处理；相反，处理“前比后高”时，前面的孩子评分更高，应该从后向前遍历；小技巧： 从后向前处理时，每个孩子最终糖果数已经被确定，所以可以直接累加，省去了最后再遍历一遍累加的开销。
860. 柠檬水找零
406. 根据身高重建队列
Note: 本题主要考察容器的使用（虽然思路也并不直接）。先将所给容器按照身高h从大到小的顺序排列，对于相同身高的，k值小的在前面，因为身高相同者排在前面的会对排在后面的人的k值产生+1的影响。

static bool cmp(vector<int>& a, vector<int>&b) {
    if (a[0] == b[0]) return a[1] < b[1];
    return a[0] > b[0];
}

之后按照该顺序，依次将各人的数据按k值插入新容器，这里的原理是：每个元素按k插入时，列表中必定只有身高比他高的人，那么此时他的k（身高≥他的人的数量）就是他在列表中的最终位置，后面插入的人身高一定比他低（如果是相同身高，后面的人k值肯定是更大的，说明后面插入的人就应该插在他后面），不会影响他的k值。另外在容器的选择上，这里选择list而非vector，因为vector在插入时需要动态扩容，并拷贝原来数据到新空间，每次插入的总复杂度是

O(n)（顺序表插入的复杂度）* O(n)（扩容拷贝的复杂度）= O(n2)

而链表list插入时间为O(1)，不需要扩容，每次插入前需要O(n)时间找到插入点（与vector不同，其迭代器不是原始指针，而是原始指针的封装类，只提供了++运算符），因此每次插入总复杂度O(1)。
452. 用最少数量的箭引爆气球
435. 无重叠区间
Note: 452和435比较相似，都是有关区间交集问题。注意这里只关心区间数量，故不需要处理左边界，所以按右边界排序会更好，如果按左边界排序，在遇到重叠区间时需要更新右端点为两个右边界最小值；而按右边界排序时，在遇到重叠区间时无需更新右端点，因为右边界是从小到大排列的，那么此时相比于直接统计重叠区间个数（直接得出答案），更好的做法是统计非重叠区间个数，最后用n减去非重叠区间个数，这样可以省去一次else（因为在遇到重叠区间时什么也不用做）。
763. 划分字母区间
Note: 主要思路是不断比较当前索引i与当前遇到过的所有字符的最后出现位置的最大值max(last[0:i])的大小，当他们相等时，说明找到一段分割，类似于45. 跳跃游戏II，都是最大覆盖范围的贪心思想，当走到最大覆盖范围时，进行下一次寻找。
56. 合并区间
Note: 由于本题需要具体区间范围，因此必须对左边界排序，并且为方便起见，直接将第一个区间放到答案数组中，之后更新右边界（所以必须按左边界排序）或者放入新的区间。
738. 单调递增的数字
Note: 注意本题需要从后往前遍历，发现右数字小于左数字则将左数字-1（若从左往右遍历，则再次操作后应该重新从头检查一遍数字是否递增，从右往左则不会），然后维护一个flag来记录最长递增数字序列的终点（如果发生右<左的情况，那么更新flag为右索引，那么最终flag是最长递增数字序列右边的第一个数），这段序列上的数组不需要任何改变，因为他本来就是递增的，而从flag开始，数字序列不再递增，为了保持结果数字最大，flag以及以后得数字应该全部变成9，由于flag左边第一个数字是最长递增数字序列的最后一位，其在遍历时已经-1，因此结果数字一定是小于等于原数的。
968. 监控二叉树
Note: 本道为hard题，关键难点在于如何贪心以及遍历整棵树。最好的办法是从下往上遍历而非从上往下遍历，因为我们必须保证叶子节点没有摄像头，否则，摄像头的数量会变为两倍。所以选择后序遍历，方便自底向上传递信息。对于贪心策略，我们需要状态转移，对于树中每个节点（包括空节点）设置3个状态：无覆盖（记为0），有摄像头（记为1），以及无摄像头但有覆盖（记为2），那么每个节点是否需要摄像头就可以自底向上传递。
然后确定状态转移方程：

  1. 如果两子节点均有覆盖（状态为2），那么该节点应为无覆盖（状态0），因为它不应设置摄像头（否则浪费），并且它并没有被下面节点覆盖（我们是从下而上遍历）。
  2. 如果至少一个子节点为无覆盖（状态0），那么该节点必须有摄像头（状态1），否则会出现子节点覆盖不到的情况。
  3. 如果至少一个子节点为有摄像头（状态1），那么该节点显然是已覆盖（状态2）。

这里情况2比情况3优先的原因是，必须先保证整颗树都被覆盖，然后才去追求摄像头数量的最小化。此外还需注意，如果在整颗树遍历完毕后，根节点未覆盖（状态为0），那么需要额外设置一个摄像头。