理论基础
本质
选择每一阶段的局部最优解，达到全局最优。
如果找到局部最优然后退出整体最优，就是贪心。
一般步骤
将问题分解为若干个子问题
找出适合的贪心策略
求解每一个子问题的最优解
将局部最优解堆叠成全局最优解
简单题目
分发饼干：力扣455
局部最优解：大饼干给胃口大的，充分利用饼干尺寸喂饱一个；全局最优：尽可能喂饱更多的小孩。
class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {//胃口排序sort(g.begin(),g.end());//饼干排序sort(s.begin(),s.end());//先遍历胃口，再遍历饼干int index=s.size()-1;//饼干下标int result=0;//记录返回结果，几个孩子能满足条件for(int i=g.size()-1;i>=0;i--){if(index>=0&&s[index]>=g[i]){ //饼干大于胃口 喂饼干index--;result++;}}return result;}
};K次取反后最大化的数组和：力扣1005
局部最优：让绝对值大的负数变为正数，当前数值达到最大；整体最优：整个数组和达到最大
局部最优：只找数值最小的正整数进行反转；整体最优：整个数组和达到最大
class Solution {
public:static bool cmp(int a,int b){return abs(a)>abs(b);}int largestSumAfterKNegations(vector<int>& nums, int k) {//1.排序sort(nums.begin(),nums.end(),cmp);//2.从后向前遍历，如果小于0，就变为正数且k--for(int i=0;i<nums.size();i++){if(nums[i]<0&&k>0){nums[i]*=-1;k--;}}//3.如果k>0，反复反转数值最小的元素，直到k=0结束if(k%2==1) nums[nums.size()-1]*=-1;int result=0;for(int i=0;i<nums.size();i++){result+=nums[i];}return result;}
};柠檬水找零：力扣860
账单是5，直接收下
账单是10，消耗一个5，增加一个10
账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5
美元10只能给账单20找零，而美元5可以给账单10和账单20找零，美元5更万能
局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零
class Solution {
public:bool lemonadeChange(vector<int>& bills) {int five=0,ten=0,twenty=0;for(int i=0;i<bills.size();i++){//情况一：收到五美元if(bills[i]==5){five++;}//情况二：收到十美元if(bills[i]==10){if(five<=0){return false;//直接结束了}five--;ten++;}//情况三：收到而是美元if(bills[i]==20){//解决一：十美元+五美元 ！优先考虑if(five>0&&ten>0){five--;ten--;twenty++;}//解决二：三张五美元！其次考虑else if(five>=3){five=five-3;}else{return false;}}}return true;}
};##遇到感觉没有思路的题目，可以静下心来把能遇到的情况分析一下，只要分析到具体情况了，一下子就豁然开朗了。
中等题目
序列问题
摆动序列：力扣376
局部最优：删除单调坡度上的结点（不包含单调坡度两端的结点），那么这个坡度就可以有两个局部峰值；整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
需要考虑三种情况：
上下坡中有平坡
数组首位两端
单调坡度有平坡
class Solution {
public:int wiggleMaxLength(vector<int>& nums) {if(nums.size()<=1) return nums.size();//不满足要求，直接返回长度int curDiff=0;//当前一对差值int preDiff=0;//前一对差值int result=1;//记录峰值个数，序列默认最右边有一个峰值for(int i=0;i<nums.size()-1;i++){curDiff=nums[i+1]-nums[i];//当前//出现峰值的情况if((preDiff<=0&&curDiff>0)||(preDiff>=0&&curDiff<0)){result++;//峰值preDiff=curDiff;//只在摆动的时候更新prediff}}return result;}
};**其实没有特别明白，但给完思路以后可以写出代码
单调递增的数字：力扣738
贪心解决股票问题
买卖股票的最佳时机：力扣122
局部最优：收集每天的正利润；全局最优：获得最大利润
class Solution {
public:int maxProfit(vector<int>& prices) {int result=0;//记录结果for(int i=1;i<prices.size();i++){//从1开始：从第二天开始才出现利润result+=max(prices[i]-prices[i-1],0);//只收集正利润，不收集负利润}return result;}
};买卖股票的最佳时机含手续费：力扣714
两个维度权衡问题
分发糖果：：力扣135
要确定一边之后，再确定另一边
先确定右边评分大于左边的情况
局部最优：只要右边评分比左边大，右边的孩子就多一个糖果，全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果
确定左孩子大于右孩子的情况
局部最优：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优：相邻的孩子中，评分高的孩子获得更多的糖果
class Solution {
public:int candy(vector<int>& ratings) {vector<int> candyvec(ratings.size(),1);candyvec[0]=1;//从前向后遍历for(int i=1;i<ratings.size();i++){if(ratings[i]>ratings[i-1]){candyvec[i]=candyvec[i-1]+1;}}//从后向前遍历for(int i=ratings.size()-2;i>=0;i--){if(ratings[i]>ratings[i+1]){candyvec[i]=max(candyvec[i],candyvec[i+1]+1);}}int result=0;//收集结果for(int i=0;i<candyvec.size();i++){result+=candyvec[i];}return result;}
};根据身高重建队列：力扣406
两个维度，h和k，看到这种题目一定要想如何确定一个维度，然后再按照另一个维度重新排列
按照身高从大到小排序后：
局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性
全局最优：最后都做完插入操作，整个队列满足题目队列属性
class Solution {
public://按照h的顺序由大到小进行排序static bool cmp(const vector<int> a,const vector<int> b){//当元素0相等的时候，按照k的大小，k大的在后面if(a[0]==b[0]){return a[1]<b[1];}return a[0]>b[0];}vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {sort(people.begin(),people.end(),cmp);//排序vector<vector<int>> que;for(int i=0;i<people.size();i++){int position=people[i][1];//插入的位置在哪que.insert(que.begin()+position,people[i]);}return que;}
};有点难度
区间问题
跳跃游戏：力扣55
转化为跳跃覆盖范围究竟可不可以覆盖到终点
局部最优解：每次最大跳跃步数（得到最大覆盖范围）；整体最优解：最后得到整体最大覆盖范围，看能否到达终点。
class Solution {
public:bool canJump(vector<int>& nums) {int cover=0;if(nums.size()==1) return true;//如果只有一个元素，直接就能到达for(int i=0;i<=cover;i++){cover=max(cover,nums[i]+i);if(cover>=nums.size()-1) return true;}return false;}
};跳跃游戏ii：力扣45
局部最优：当前可移动距离尽可能夺走，如果还没到终点，部署再加一；整体最优：一步尽可能多走，从而达到最小步数。但解题时，要从覆盖范围出发，不管怎么跳跃，覆盖范围内一定是可以跳到的，以最小的部署增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最小步数。
需要统计：当前这一步的最大覆盖和下一步最大覆盖
class Solution {
public:int jump(vector<int>& nums) {if(nums.size()==1) return 0;//只有一个元素，直接可以走到最后int curDistance=0;//当前距离int ans=0;//最大步数int nextDistance=0;//下一步的距离for(int i=0;i<nums.size();i++){nextDistance=max(nextDistance,nums[i]+i);//更新下一步覆盖最远距离if(i==curDistance){//如果遇到if(curDistance<nums.size()-1){//不是终点ans++;curDistance=nextDistance;//更新当前覆盖最远距离的下标if(nextDistance>=nums.size()-1) break;//下一步的覆盖范围已经可以到达终点 循环结束}else break;//是终点 直接结束}}return ans;}
};用最少数量的箭引爆气球：力扣452
局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。
为了让气球尽可能的重叠，需要对数组进行排序
class Solution {
public:static bool cmp(const vector<int> &a,const vector<int> &b){return a[0]<b[0];}int findMinArrowShots(vector<vector<int>>& points) {if(points.size()==0) return 0;int result=1;//起码需要一只箭sort(points.begin(),points.end(),cmp);for(int i=1;i<points.size();i++){if(points[i][0]>points[i-1][1]){//两个不挨着 需要+1result++;}else{//两个挨着 更新最小边界points[i][1]=min(points[i-1][1],points[i][1]);}}return result;}
};无重叠区间：力扣435
按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
class Solution {
public:// 按照区间右边界排序static bool cmp (const vector<int>& a, const vector<int>& b) {return a[1] < b[1];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {if(intervals.size()==0) return 0;sort(intervals.begin(),intervals.end(),cmp);//排序int result=1;//记录非交叉的区间int end=intervals[0][1];//分割点：第一个区间的结束位置//从前往后遍历（已经按照右边排序）for(int i=1;i<intervals.size();i++){if(end<=intervals[i][0]){result++;end=intervals[i][1];}}return intervals.size()-result;}
};划分字母区间：力扣763
在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。
统计每一个字符最后出现的位置
从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
class Solution {
public:vector<int> partitionLabels(string s) {int hash[27]={0};//hash[i]是字符最后出现的位置for(int i=0;i<s.size();i++){hash[s[i]-'a']=i;//最远出现的位置}int right=0;int left=0;//分割字符串vector<int> result;for(int i=0;i<s.size();i++){right=max(right,hash[s[i]-'a']);if(i==right){result.push_back(right-left+1);left=i+1;}}return result;}
};*对代码有不明白的地方
合并区间：力扣56
左边界排序，排序之后局部最优：每次合并都取最大的右边界，这样就可以合并更多的区间了，整体最优：合并所有重叠的区间。
class Solution {
public:// 按照区间左边界从小到大排序static bool cmp (const vector<int>& a, const vector<int>& b) {return a[0] < b[0];}vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> result;if(intervals.size()==0) return result;sort(intervals.begin(),intervals.end(),cmp);bool flag=false;//表示最后一个区间是否合并进去了int len=intervals.size();for(int i=1;i<len;i++){int start=intervals[i-1][0];//合并的开始位置int end=intervals[i-1][1];//合并的结束位置while(i<len&&intervals[i][0]<=end){//满足合并的情况//更新右区间end=max(end,intervals[i][1]);//最后一个区间也合并了的情况if(i==len-1) flag=true;i++;//继续寻找下一个合并区间}result.push_back({start,end});}//如果最后的区间不合并if(flag==false){result.push_back({intervals[len-1][0],intervals[len-1][1]});}return result; }
};其他
最大子序和：力扣53
局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算”连续和“，因为附属加上下一个元素“连续和”只会越来越小；全局最优：选取最大“连续和”。局部最优的情况下，记录最大的”连续和“，可以推出全局最优。
class Solution {
public:int maxSubArray(vector<int>& nums) {int result=INT32_MIN;int count=0;for(int i=0;i<nums.size();i++){count+=nums[i];//区间累计的最大值（相当于不断确定最大子序列的终止位置if(count>result) result=count;//相当于重置最大子序列的开始位置，因为负数会拉低总和if(count<=0) count=0;}return result;}
};加油站：力扣134
如果gas的总和小于cost的综合，无论从哪里出发，都跑不了一圈
rest=gas-cost为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发油从未中断，0就是起点。
如果累加的最小值是负数，汽车就要从非0结点出发，从后向前，看哪个结点能将这个负数填平，能把这个负数填平的结点就是出发结点
class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int curSum=0;int minv=INT_MAX;//计算值for(int i=0;i<gas.size();i++){int rest=gas[i]-cost[i];curSum+=rest;if(curSum<minv){minv=curSum;}}if(curSum<0) return -1;//gas总和小于cost的总和哪里都到不了 情况1if(minv>=0) return 0;//0是起点 情况2//累加的最小值是负数，得从非0结点出发，看哪个结点能把负数填平，能填平的哪个结点就是出发结点for(int i=gas.size()-1;i>=0;i--){int rest=gas[i]-cost[i];minv+=rest;if(minv>=0){return i;//找到能填平的点}}return -1;}
};
