blog_贪心算法

贪心算法每步都选当前最优真的能赢吗算法四大件之二贪心 | 适用场景具有贪心选择性质、最优子结构一、什么是贪心算法贪心算法Greedy Algorithm的核心思想每一步都做出当前看来最好的选择不考虑全局。就像去买零食你每经过一个货架都拿最想吃的那一样不管最后会不会后悔没拿别的。贪心算法解题框架 1. 把问题分解成若干个步骤 2. 每个步骤做出一个选择贪心选择 3. 做出选择后原问题变成一个新的子问题 4. 重复直到问题解决贪心算法的两个关键性质性质含义判断方法贪心选择性质全局最优解可以通过一系列局部最优贪心选择来达到证明假设贪心选择不是最优的推出矛盾最优子结构问题的最优解包含其子问题的最优解动态规划也需要这个性质⚠️重要提醒贪心算法不是对所有问题都有效只有满足上述两个性质的问题贪心才能得到全局最优解。贪心 vs 动态规划对比项贪心算法动态规划决策方式每步只选当前最优考虑所有子问题选全局最优是否有后效性无后效前面选了就定了可能有后效需要记录状态时间复杂度通常 O(n log n) 或 O(n)通常 O(n²) 或更高正确性需要证明一定正确只要状态转移对适用场景满足贪心选择性质有重叠子问题 最优子结构二、经典例题详解例题1力扣455. 分发饼干贪心入门必做题目链接https://leetcode.cn/problems/assign-cookies/难度简单 ⭐标签贪心、排序题目描述假设你是一位很棒的家长想要给你的孩子们一些小饼干。但是每个孩子最多只能给一块饼干。每个孩子有一个胃口值g[i]每块饼干有一个尺寸s[j]。如果s[j] g[i]就可以把这块饼干分给孩子i这个孩子会感到满足。你的目标是尽可能满足越多数量的孩子。示例输入g [1,2,3], s [1,1] 输出1 解释饼干尺寸为1的只能满足胃口为1的孩子所以输出1。 输入g [1,2], s [1,2,3] 输出2 解释可以满足两个孩子输出2。思路分析贪心策略用最小的能满足孩子的饼干去满足胃口最小的孩子。为什么这样贪心是对的如果一块大饼干可以满足胃口小的孩子那它也可能满足胃口大的孩子但如果用它满足了胃口小的胃口大的孩子可能就没饼干吃了所以大饼干要留给大胃口的孩子步骤把孩子胃口数组g排序从小到大把饼干尺寸数组s排序从小到大用双指针 greedy 匹配孩子胃口[1, 2, 3] (已排序) 饼干尺寸[1, 2, 3] (已排序) ↓ 饼干1(尺寸1) → 孩子1(胃口1) 满足 饼干2(尺寸2) → 孩子2(胃口2) 满足 饼干3(尺寸3) → 孩子3(胃口3) 满足 满足孩子数 3代码实现C语言#includestdio.h#includestdlib.hintcmp(constvoid*a,constvoid*b){return(*(int*)a)-(*(int*)b);}intfindContentChildren(int*g,intgSize,int*s,intsSize){qsort(g,gSize,sizeof(int),cmp);qsort(s,sSize,sizeof(int),cmp);intchild0;intcookie0;while(childgSizecookiesSize){if(s[cookie]g[child]){child;}cookie;}returnchild;}intmain(){intg[]{1,2,3};ints[]{1,1};intresultfindContentChildren(g,3,s,2);printf(满足的孩子数 %d\n,result);intg2[]{1,2};ints2[]{1,2,3};resultfindContentChildren(g2,2,s2,3);printf(满足的孩子数 %d\n,result);return0;}代码实现C 语言#includeiostream#includevector#includealgorithmusingnamespacestd;classSolution{public:intfindContentChildren(vectorintg,vectorints){sort(g.begin(),g.end());sort(s.begin(),s.end());intchild0;intcookie0;while(childg.size()cookies.size()){if(s[cookie]g[child]){child;}cookie;}returnchild;}};intmain(){Solution sol;vectorintg{1,2,3};vectorints{1,1};intresultsol.findContentChildren(g,s);cout满足的孩子数 resultendl;vectorintg2{1,2};vectorints2{1,2,3};resultsol.findContentChildren(g2,s2);cout满足的孩子数 resultendl;return0;}复杂度分析指标复杂度说明时间复杂度O(n log n m log m)排序占主导n是孩子数m是饼干数空间复杂度O(1) 或 O(log n)排序的栈空间快排递归栈例题2力扣376. 摆动序列贪心经典题目链接https://leetcode.cn/problems/wiggle-subsequence/难度中等 ⭐⭐标签贪心、动态规划题目描述如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为摆动序列。给定一个整数数组nums返回最长摆动子序列的长度。示例输入nums [1,7,4,9,2,5] 输出6 解释整个序列本身就是摆动序列差6,-3,5,-7,3长度为6。 输入nums [1,17,5,10,13,15,10,5,16,8] 输出7 解释最长摆动子序列是 [1,17,10,13,10,16,8]不一定连续思路分析贪心策略我们只需要保留峰值点去掉单调坡上的中间点数组[1, 17, 5, 10, 13, 15, 10, 5, 16, 8] 差值 16 -12 5 3 2 -5 -5 11 -8 ↑ ↑ ↑ ↑ 峰值保留 单调坡去掉中间的点核心观察如果有一段单调递增如 10→13→15我们只需要保留两端10 和 15中间的 13 去掉不影响摆动性质用上下坡的概念记录当前是上坡还是下坡状态切换时计数1代码实现C语言#includestdio.hintwiggleMaxLength(int*nums,intnumsSize){if(numsSize2)returnnumsSize;intstart0;while(startnumsSize-1nums[start]nums[start1]){start;}if(startnumsSize-1)return1;intprevDiffnums[start1]-nums[start];intcount2;for(intistart2;inumsSize;i){intdiffnums[i]-nums[i-1];if((diff0prevDiff0)||(diff0prevDiff0)){count;prevDiffdiff;}}returncount;}intmain(){intnums[]{1,7,4,9,2,5};printf(最长摆动序列长度 %d\n,wiggleMaxLength(nums,6));intnums2[]{1,17,5,10,13,15,10,5,16,8};printf(最长摆动序列长度 %d\n,wiggleMaxLength(nums2,10));return0;}代码实现C 语言#includeiostream#includevectorusingnamespacestd;classSolution{public:intwiggleMaxLength(vectorintnums){intnnums.size();if(n2)returnn;intstart0;while(startn-1nums[start]nums[start1]){start;}if(startn-1)return1;intprevDiffnums[start1]-nums[start];intcount2;for(intistart2;in;i){intdiffnums[i]-nums[i-1];if((diff0prevDiff0)||(diff0prevDiff0)){count;prevDiffdiff;}}returncount;}};intmain(){Solution sol;vectorintnums{1,7,4,9,2,5};cout最长摆动序列长度 sol.wiggleMaxLength(nums)endl;return0;}例题3力扣134. 加油站贪心经典难题题目链接https://leetcode.cn/problems/gas-station/难度中等 ⭐⭐标签贪心题目描述在一条环路上有n个加油站其中第i个加油站有汽油gas[i]升。你有一辆油箱容量无限的汽车从第i个加油站开往第i1个加油站需要消耗汽油cost[i]升。你从其中的一个加油站出发开始时油箱为空。给定两个整数数组gas和cost如果你可以按顺序走遍所有加油站一圈则返回出发时加油站的索引否则返回-1。示例输入gas [1,2,3,4,5], cost [3,4,5,1,2] 输出3 解释从索引3出发油箱有4升够跑到索引4剩3...可以跑完一圈。思路分析数学结论如果sum(gas) sum(cost)肯定无解直接返回 -1如果有解从某个起点出发如果跑到某个站油量变成负数那么从这个起点到这个站之间的所有站作为起点都不可能成功直接从下一个站重新开始gas [1, 2, 3, 4, 5] cost [3, 4, 5, 1, 2] diff [-2,-2,-2, 3, 3] 每次剩下的油 从索引0出发 站0剩 -2 → 不行所以从站0、站1、站2出发都不行 从索引3出发 站3剩 3 站4剩 6 站0剩 4 绕回来了 站1剩 2 站2剩 0 成功为什么中间的站都不行假设从站i出发开到站k时油量变负。如果从站i1出发到站k时的油量只会更少因为少加了gas[i]少花了cost[i]所以也一定会失败。因此可以直接跳过i到k之间的所有站代码实现C语言#includestdio.hintcanCompleteCircuit(int*gas,intgasSize,int*cost,intcostSize){inttotalGas0;inttotalCost0;inttank0;intstart0;for(inti0;igasSize;i){totalGasgas[i];totalCostcost[i];tankgas[i]-cost[i];if(tank0){starti1;tank0;}}if(totalGastotalCost)return-1;returnstart;}intmain(){intgas[]{1,2,3,4,5};intcost[]{3,4,5,1,2};printf(出发索引 %d\n,canCompleteCircuit(gas,5,cost,5));intgas2[]{2,3,4};intcost2[]{3,4,3};printf(出发索引 %d\n,canCompleteCircuit(gas2,3,cost2,3));return0;}代码实现C 语言#includeiostream#includevectorusingnamespacestd;classSolution{public:intcanCompleteCircuit(vectorintgas,vectorintcost){inttotalGas0;inttotalCost0;inttank0;intstart0;for(inti0;igas.size();i){totalGasgas[i];totalCostcost[i];tankgas[i]-cost[i];if(tank0){starti1;tank0;}}if(totalGastotalCost)return-1;returnstart;}};intmain(){Solution sol;vectorintgas{1,2,3,4,5};vectorintcost{3,4,5,1,2};cout出发索引 sol.canCompleteCircuit(gas,cost)endl;return0;}三、贪心算法总结什么时候用贪心优先考虑贪心如果题目有明显的选择过程选或不选、选哪个排序后问题变得更简单动态规划写出来太慢O(n²) 会超时不要用贪心如果当前选择会影响后面的选择有后效性无法证明贪心选择性质常用贪心套路套路典型题目核心思想排序 双指针455.分发饼干、435.无重叠区间排序后贪心匹配按差分正负切换计数376.摆动序列只保留峰值跳过无效区间134.加油站、53.最大子数组和数学结论 贪心优先队列堆502.IPO、1834.单线程CPU每次选当前最优如果觉得这篇博客对你有帮助欢迎点赞收藏下一篇我们将讲解「回溯法」