贪心算法总结（1）_贪心算法的反证与交换论证
一、贪心算法简介
常用方法：交换论证法、数学归纳法、反证法、分类讨论
二、柠檬水找零（交换论证法）
. - 力扣（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&&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<n-1;++i){ int right=nums[i+1]-nums[i]; if(right==0) continue;//跳过相等的情况 if(right*left<=0) ++ret; left=right; } return ret+1; //算上最后一个 }};六、最长递增子序列（交换论证）
. - 力扣（LeetCode）
贪心+二分
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]<nums[i]) left=mid+1; else right=mid; } ret[left]=nums[i]; } return ret.size(); }};七、递增的三元子序列
. - 力扣（LeetCode）
贪心：
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; }};八、最长连续递增子序列
. - 力扣（LeetCode）
贪心+滑动窗口：
class Solution {public: int findLengthOfLCIS(vector& nums) { //贪心+双指针 int ret=0; int n=nums.size(); for(int i=0;i<n;){ int j=i+1; while(jnums[j-1]) ++j; ret=max(j-i,ret); i=j; } return ret; }}; 
