一、贪心算法简介

常用方法：交换论证法、数学归纳法、反证法、分类讨论 

 二、柠檬水找零（交换论证法）

. - 力扣（LeetCode）

class Solution { public:     bool lemonadeChange(vector& bills) {          int five=0,ten=0;          for(auto&e:bills)             if(e==5) ++five;             else if(e==10)             {                 if(five==0) return false;                 --five,++ten;             }             else //贪心策略             {                 if(five&&ten) --five,--ten;                 else if(five>=3) five-=3;                 else return false;             }          return true;     }     //交换论证法、数学归纳法和反证法常用的策略 };

三、将数组减半的最小操作次数（交换论证法）

. - 力扣（LeetCode）

class Solution { public:     int halveArray(vector& nums) {         priority_queue q(nums.begin(),nums.end());         double sum=accumulate(nums.begin(),nums.end(),0.0);         int ret=0;         sum/=2.0;         while(sum>0)         {             double t=q.top()/2.0;             q.pop();             sum-=t;             q.push(t);             ++ret;         }         return ret;     } };

四、最大数（排序规则理解+全序性证明）

. - 力扣（LeetCode）

class Solution { public:     string largestNumber(vector& nums) {        //贪心策略 先转化成字符串 然后利用字典序排序        vector strs;        strs.reserve(nums.size());//提前扩容 小优化        for(auto&e:nums) strs.emplace_back(to_string(e));        sort(strs.begin(),strs.end(),[](const string&s1,const string&s2)        {                return s1+s2>s2+s1;//大的在前面        });        //按顺序加入到ret中返回         string ret;        for(auto&s:strs) ret+=s;        //细节处理:前导0 除非都是0才会出现前导0  所以我们只需要当出现前导0的时候，返回"0"即可        if(ret[0]=='0') return "0";        return ret;     }     //全序关系  一个集合中任意选出两个元素 如果在你定义的比较规则下能够满足全序关系                 //我们就说这个集合是可以排序的         //1、完全性 可以推测出他的大小关系（a>=b a<=b）         //2、反对称性 a>=b&&b>=a  ——>a==b   a前和b前无所谓(唯一性)         //3、传递性 a>=b  b>=c a>=c };

五、摆动序列（反证法）

. - 力扣（LeetCode）

class Solution { public:     int wiggleMaxLength(vector& nums)      {         int n=nums.size();         if(n<2) return n;       //总是选择当前的最优策略        int left=0,ret=0; //left表示左边的状态        for(int i=0;i

class Solution { public:     int lengthOfLIS(vector& nums)      {        //贪心+二分        int n=nums.size();        vector ret;        ret.emplace_back(nums[0]);        for(int i=1;iret.back()) ret.emplace_back(nums[i]);          //否则就用二分          else           {             int left=0,right=ret.size()-1;             while(left>1;                 if(ret[mid]

class Solution { public:     bool increasingTriplet(vector& nums) {      //贪心策略      int n=nums.size();      if(n<3) return false;      int first=nums[0];      int second=INT_MAX;      for(int i=1;isecond) return true;         else if(nums[i]>first) second=nums[i];         else first=nums[i];//否则我肯定比较小 就得更新first      return false;     } };

class Solution { public:     int findLengthOfLCIS(vector& nums) {      //贪心+双指针      int ret=0;      int n=nums.size();      for(int i=0;inums[j-1]) ++j;        ret=max(j-i,ret);        i=j;      }      return ret;     } };