贪心基础
贪心(Greedy)常用于解决最优问题，以期通过某种策略获得一系列局部最优解、从而求得整体最优解。
贪心从局部最优角度考虑，只适用于具备无后效性的问题，即某个状态以前的过程不影响以后的状态、紧接下来的状态仅与当前状态有关。和分治、动态规划一样，贪心是一种思路，不是解决某类问题的具体方法。
应用贪心的关键，是甄别问题是否具备无后效性、找到获得局部最优的策略。有的问题比较浅显，例如一道找零钱的题目 LeetCode 860. Lemonade Change：
// 860. Lemonade Change bool lemonadeChange(vector<int>& bills) { int five=0,ten=0; for(auto i:bills){ if(i==5) five++; else if(i==10) ten++,five--; else if(ten>0) ten--,five--; else five-=3; if(five<0) return false; } return true; }
以上策略的核心就是每轮找零用最大的面额、保留尽量多5元纸币。
相关LeetCode题：
122. Best Time to Buy and Sell Stock II 题解
1090. Largest Values From Labels 题解
984. String Without AAA or BBB 题解
但一些问题不那么直观，需要深一层考虑局部最优的策略，例如 LeetCode题目 55. Jump Game：
// 55. Jump Game bool canJump(vector<int>& nums) { int res=0; for(int i=0;i<=res;i++){ res=max(res,i+nums[i]); if(res>=nums.size()-1) return true; } return false; }
以上每轮更新最远可以到达的位置。
相关LeetCode题：
861. Score After Flipping Matrix 题解
921. Minimum Add to Make Parentheses Valid 题解
1053. Previous Permutation With One Swap 题解
贪心与优先级队列
一些贪心策略是每轮获取极值处理，这时可以借助于优先级队列，关于优先级队列详见：
算法与数据结构基础 - 堆(Heap)和优先级队列(Priority Queue)
相关LeetCode题：
1005. Maximize Sum Of Array After K Negations 题解
1167. Minimum Cost to Connect Sticks 题解
358. Rearrange String k Distance Apart 题解
贪心与排序
类似地，也可以通过排序获得极值以用于贪心策略，关于排序详见：
相关LeetCode题：
406. Queue Reconstruction by Height 题解
452. Minimum Number of Arrows to Burst Balloons 题解
435. Non-overlapping Intervals 题解
优先级队列和排序还可以一起应用于贪心策略（这类贪心策略我称之为多层贪心策略），例如针对二维数据，先对第一维排序、然后通过优先级队列对第二维取极值。