贪心法，又称贪心算法，贪婪算法，在对问题求解时，总是做出在当前看来最好的选择，期望通过每个阶段的局部最优选择达到全局最优，但结果不一定最优
适用场景：简单的说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解，就能用贪心算法的到最后的最优解，这种子问题最优解称为最优子结构
贪心算法与动态规划的不同点在于它对每个子问题的解决方案都做出当前的最优选择，不能回退，而动态规划会保留之前的运算结果，并根据之前的结果进行选择，有回退的功能，贪心是动态规划的理想化的情况。
js:
varmaxProfit=function(prices){constn=prices.length;constdp=newArray(n).fill(0).map((v)=>newArray(2).fill(0));//初始化状态数组(dp[0][0]=0),(dp[0][1]=-prices[0]);//3.定义初始值for(leti=1;i varmaxProfit=function(prices){letans=0;letn=prices.length;for(leti=1;i varfindContentChildren=function(g,s){g=g.sort((a,b)=>a-b);s=s.sort((a,b)=>a-b);//排序数组letresult=0;letindex=s.length-1;for(leti=g.length-1;i>=0;i--){//从胃口大的小孩开始满足if(index>=0&&s[index]>=g[i]){result++;//结果加1index--;}}returnresult;};java： js： //leetcode执行超时复杂度过高vareraseOverlapIntervals=function(intervals){if(!intervals.length){return0;}intervals.sort((a,b)=>a[0]-b[0]);//按左边界排序constn=intervals.length;constdp=newArray(n).fill(1);//初始化dp数组for(leti=1;i vareraseOverlapIntervals=function(intervals){if(!intervals.length){return0;}//按右边界排序，然后从左往右遍历，右边界结束的越早，留给后面的区间的空间就越大，不重合的区间个数就越多intervals.sort((a,b)=>a[1]-b[1]);constn=intervals.length;letright=intervals[0][1];//right初始化为第一个区间的右边界letans=1;//最多的不重合区间的个数for(leti=1;i classSolution{publicinteraseOverlapIntervals(int[][]intervals){if(intervals.length==0){return0;}Arrays.sort(intervals,newComparator 以这一题为例： functioncanJump(nums){letdp=newArray(nums.length).fill(false);//初始化dpdp[0]=true;//第一项能到达for(leti=1;i varcanJump=function(nums){if(nums.length===1)returntrue;//长度为1直接就是终点letcover=nums[0];//能覆盖的最远距离for(leti=0;i<=cover;i++){cover=Math.max(cover,i+nums[i]);//当前覆盖距离cover和当前位置加能跳跃的距离中取一个较大者if(cover>=nums.length-1){//覆盖距离超过或等于nums.length-1说明能到达终点returntrue;}}returnfalse;//循环完成之后还没返回true就是不能达到终点};java： varnumRescueBoats=function(people,limit){people.sort((a,b)=>(a-b));letans=0,left=0,//左指针初始化在0的位置right=people.length-1//右指针初始化在people.length-1的位置while(left<=right){//两指针向中间靠拢遍历//当people[left]+people[right--])<=limit表示左右两边的人可以一起坐船然后让left++right--//如果两人坐不下，那只能让重的人先坐一条船也就是让right--if((people[left]+people[right--])<=limit){left++} ans++}returnans};java： varfindMinArrowShots=function(points){if(!points.length){return0;}points.sort((a,b)=>a[1]-b[1]);//按照区间结尾排序letpos=points[0][1];letans=1;for(letballoonofpoints){if(balloon[0]>pos){//如果后面一个区间的开始大于前一个区间的结尾就需要新增一支箭pos=balloon[1];//更新pos为新的区间的结尾ans++;}}returnans;};java： varcanCompleteCircuit=function(gas,cost){lettotalGas=0;lettotalCost=0;for(leti=0;i varlemonadeChange=function(bills){letfive=0,ten=0;for(constbillofbills){if(bill===5){//面值为5直接可以兑换柠檬水five+=1;}elseif(bill===10){//面值为10兑换柠檬水还需要找5元if(five===0){returnfalse;}five-=1;ten+=1;}else{//面值为20兑换柠檬水需要找3个5元或一个10元一个5元if(five>0&&ten>0){five-=1;ten-=1;}elseif(five>=3){five-=3;}else{returnfalse;}}}returntrue;};