贪心贪心 我们喜欢你
贪心
局部最优推全局最优
贪心没有什么套路，就是要多练啊啊啊
了解相关场景和题型
1.分发饼干455. 分发饼干 - 力扣（LeetCode）
classSolution{publicintfindContentChildren(int[]g,int[]s){Arrays.sort(g);Arrays.sort(s);inti=0;for(intsNum:s){//依次喂饱胃口小的if(i<g.length&&g[i]<=sNum){i++;}}returni;}}2.摆动序列376. 摆动序列 - 力扣（LeetCode）
//就是找峰值 找到局部最大值和局部最小值
classSolution{publicintwiggleMaxLength(int[]nums){if(nums.length<=1)returnnums.length;intcount=1;//记录初始长度Booleanflag=null;for(intj=1;j<nums.length;j++){intcur=nums[j]-nums[j-1];if(cur==0){continue;}booleancurDiff=cur>0;if(flag==null||flag!=curDiff){count++;}flag=curDiff;}returncount;}}3.最大子序和53. 最大子数组和 - 力扣（LeetCode）
当当前的数大于之前的值的时候就重新开始
classSolution{publicintmaxSubArray(int[]nums){// 初始值：将ans和cur都设为数组第一个元素（避免全负数场景错误）intans=nums[0];intcur=nums[0];// 从第二个元素开始遍历for(inti=1;i<nums.length;i++){intnum=nums[i];// 核心逻辑：cur选择「只取当前数」或「当前数+之前累加和」的较大值// 这一步保证cur始终是「以当前元素结尾的最大子数组和」cur=Math.max(num,cur+num);// 更新全局最大和ans=Math.max(ans,cur);}returnans;}}4.买卖股票最佳时机122. 买卖股票的最佳时机 II - 力扣（LeetCode）
classSolution{publicintmaxProfit(int[]prices){//算出和前一天利润的差 因为隔两天的利润就相当于差值相加//所以我们要求的就是收集正利润 得到最好的收益int[]profits=newint[prices.length];for(inti=1;i<prices.length;i++){profits[i-1]=prices[i]-prices[i-1];}intans=0;for(intprofit:profits){if(profit>0){ans+=profit;}}returnans;}}5.跳跃游戏55. 跳跃游戏 - 力扣（LeetCode）
classSolution{publicbooleancanJump(int[]nums){//就是看往后的覆盖范围能到哪 然后覆盖范围里有没有到最终结果的intj=0;inti=0;while(i<=j){j=Math.max(i+nums[i],j);if(j>=nums.length-1){returntrue;}i++;}returnfalse;}}6.跳跃游戏Ⅱ45. 跳跃游戏 II - 力扣（LeetCode）
classSolution{publicintjump(int[]nums){intn=nums.length;if(n<2)return0;// 边界：无需跳跃intsteps=0;// 最小步数intcurrentEnd=0;// 当前步数能到达的最远边界intmaxReach=0;// 遍历过程中能到达的最远位置// 遍历到倒数第二个元素即可（到最后一个就不用跳了）for(inti=0;i<n-1;i++){maxReach=Math.max(maxReach,i+nums[i]);// 更新最远可达位置// 到达当前步数的边界，需要跳一步，更新边界if(i==currentEnd){steps++;currentEnd=maxReach;// 提前终止：当前能到末尾，无需继续遍历if(currentEnd>=n-1)break;}}returnsteps;}}7.K次数取反后最大化的数组和1005. K 次取反后最大化的数组和 - 力扣（LeetCode）
classSolution{publicintlargestSumAfterKNegations(int[]nums,intk){//先让负的全部变成正的 再排序 让最小的进行变号Arrays.sort(nums);for(inti=0;i<nums.length&&nums[i]<0&&k>0;i++){nums[i]=-nums[i];k--;}Arrays.sort(nums);if(k%2!=0){nums[0]=-nums[0];}intans=0;for(intnum:nums){ans+=num;}returnans;}}8.加油站134. 加油站 - 力扣（LeetCode）
classSolution{publicintcanCompleteCircuit(int[]gas,int[]cost){//只要总油量大于等于总消耗 那必然存在一条合理路线intn=gas.length;intcur=0;inttotal=0;intstart=0;for(inti=0;i<n;i++){intdiff=gas[i]-cost[i];total+=diff;cur+=diff;//小于0 则换位置if(cur<0){start=i+1;cur=0;}}returntotal>=0?start:-1;}}9.分发糖果
10.柠檬水找零860. 柠檬水找零 - 力扣（LeetCode）
classSolution{publicbooleanlemonadeChange(int[]bills){//每次都尽可能地找大的零钱int[]amount=newint[2];//分别代表5，10for(intbill:bills){if(bill==5)//无需找钱{amount[0]++;}else{//看有没有5块if(amount[0]<1){returnfalse;}amount[0]--;if(bill==10){amount[1]++;}elseif(bill==20){if(amount[1]>0){amount[1]--;}else{if(amount[0]>=2){amount[0]-=2;}else{returnfalse;}}}}}returntrue;}}11.根据身高重建队列406. 根据身高重建队列 - 力扣（LeetCode）
classSolution{publicint[][]reconstructQueue(int[][]people){Arrays.sort(people,newComparator<int[]>(){publicintcompare(int[]person1,int[]person2){if(person1[0]!=person2[0]){returnperson1[0]-person2[0];}else{returnperson2[1]-person1[1];}}});intn=people.length;int[][]ans=newint[n][];for(int[]person:people){intspaces=person[1]+1;for(inti=0;i<n;i++){if(ans[i]==null){--spaces;if(spaces==0){ans[i]=person;break;}}}}returnans;}}
