blog_贪心算法

贪心算法：每步都选"当前最优"，真的能赢吗？

算法四大件之二：贪心 | 适用场景：具有贪心选择性质、最优子结构

一、什么是贪心算法？

贪心算法（Greedy Algorithm）的核心思想：

每一步都做出当前看来最好的选择，不考虑全局。

就像去买零食，你每经过一个货架都拿最想吃的那一样，不管最后会不会后悔没拿别的。

贪心算法解题框架： 1. 把问题分解成若干个步骤 2. 每个步骤做出一个选择（贪心选择） 3. 做出选择后，原问题变成一个新的子问题 4. 重复，直到问题解决

贪心算法的两个关键性质

⚠️重要提醒：贪心算法不是对所有问题都有效！只有满足上述两个性质的问题，贪心才能得到全局最优解。

贪心 vs 动态规划

二、经典例题详解

例题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。

思路分析

贪心策略：用最小的能满足孩子的饼干，去满足胃口最小的孩子。

为什么这样贪心是对的？

• 如果一块大饼干可以满足胃口小的孩子，那它也可能满足胃口大的孩子
• 但如果用它满足了胃口小的，胃口大的孩子可能就没饼干吃了
• 所以：大饼干要留给大胃口的孩子！

步骤：

1. 把孩子胃口数组g排序（从小到大）
2. 把饼干尺寸数组s排序（从小到大）
3. 用双指针： greedy 匹配

孩子胃口：[1, 2, 3] (已排序) 饼干尺寸：[1, 2, 3] (已排序) ↓ 饼干1(尺寸1) → 孩子1(胃口1) 满足！ 饼干2(尺寸2) → 孩子2(胃口2) 满足！ 饼干3(尺寸3) → 孩子3(胃口3) 满足！ 满足孩子数 = 3

代码实现（C语言）

#include<stdio.h>#include<stdlib.h>intcmp(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);intchild=0;intcookie=0;while(child<gSize&&cookie<sSize){if(s[cookie]>=g[child]){child++;}cookie++;}returnchild;}intmain(){intg[]={1,2,3};ints[]={1,1};intresult=findContentChildren(g,3,s,2);printf("满足的孩子数 = %d\n",result);intg2[]={1,2};ints2[]={1,2,3};result=findContentChildren(g2,2,s2,3);printf("满足的孩子数 = %d\n",result);return0;}

代码实现（C++ 语言）

#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;classSolution{public:intfindContentChildren(vector<int>&g,vector<int>&s){sort(g.begin(),g.end());sort(s.begin(),s.end());intchild=0;intcookie=0;while(child<g.size()&&cookie<s.size()){if(s[cookie]>=g[child]){child++;}cookie++;}returnchild;}};intmain(){Solution sol;vector<int>g={1,2,3};vector<int>s={1,1};intresult=sol.findContentChildren(g,s);cout<<"满足的孩子数 = "<<result<<endl;vector<int>g2={1,2};vector<int>s2={1,2,3};result=sol.findContentChildren(g2,s2);cout<<"满足的孩子数 = "<<result<<endl;return0;}

复杂度分析

例题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语言）

#include<stdio.h>intwiggleMaxLength(int*nums,intnumsSize){if(numsSize<2)returnnumsSize;intstart=0;while(start<numsSize-1&&nums[start]==nums[start+1]){start++;}if(start==numsSize-1)return1;intprevDiff=nums[start+1]-nums[start];intcount=2;for(inti=start+2;i<numsSize;i++){intdiff=nums[i]-nums[i-1];if((diff>0&&prevDiff<0)||(diff<0&&prevDiff>0)){count++;prevDiff=diff;}}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++ 语言）

#include<iostream>#include<vector>usingnamespacestd;classSolution{public:intwiggleMaxLength(vector<int>&nums){intn=nums.size();if(n<2)returnn;intstart=0;while(start<n-1&&nums[start]==nums[start+1]){start++;}if(start==n-1)return1;intprevDiff=nums[start+1]-nums[start];intcount=2;for(inti=start+2;i<n;i++){intdiff=nums[i]-nums[i-1];if((diff>0&&prevDiff<0)||(diff<0&&prevDiff>0)){count++;prevDiff=diff;}}returncount;}};intmain(){Solution sol;vector<int>nums={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个加油站开往第i+1个加油站需要消耗汽油cost[i]升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组gas和cost，如果你可以按顺序走遍所有加油站一圈，则返回出发时加油站的索引，否则返回-1。

示例：

输入：gas = [1,2,3,4,5], cost = [3,4,5,1,2] 输出：3 解释：从索引3出发，油箱有4升，够跑到索引4（剩3），...，可以跑完一圈。

思路分析

数学结论：

1. 如果sum(gas) < sum(cost)，肯定无解，直接返回 -1
2. 如果有解，从某个起点出发，如果跑到某个站油量变成负数，那么从这个起点到这个站之间的所有站作为起点都不可能成功，直接从下一个站重新开始！

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时油量变负。
如果从站i+1出发，到站k时的油量只会更少（因为少加了gas[i]，少花了cost[i]），所以也一定会失败。
因此可以直接跳过i到k之间的所有站！

代码实现（C语言）

#include<stdio.h>intcanCompleteCircuit(int*gas,intgasSize,int*cost,intcostSize){inttotalGas=0;inttotalCost=0;inttank=0;intstart=0;for(inti=0;i<gasSize;i++){totalGas+=gas[i];totalCost+=cost[i];tank+=gas[i]-cost[i];if(tank<0){start=i+1;tank=0;}}if(totalGas<totalCost)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++ 语言）

#include<iostream>#include<vector>usingnamespacestd;classSolution{public:intcanCompleteCircuit(vector<int>&gas,vector<int>&cost){inttotalGas=0;inttotalCost=0;inttank=0;intstart=0;for(inti=0;i<gas.size();i++){totalGas+=gas[i];totalCost+=cost[i];tank+=gas[i]-cost[i];if(tank<0){start=i+1;tank=0;}}if(totalGas<totalCost)return-1;returnstart;}};intmain(){Solution sol;vector<int>gas={1,2,3,4,5};vector<int>cost={3,4,5,1,2};cout<<"出发索引 = "<<sol.canCompleteCircuit(gas,cost)<<endl;return0;}

三、贪心算法总结

什么时候用贪心？

优先考虑贪心，如果：

• 题目有明显的"选择"过程（选或不选、选哪个）
• 排序后问题变得更简单
• 动态规划写出来太慢（O(n²) 会超时）

不要用贪心，如果：

• 当前选择会影响后面的选择（有后效性）
• 无法证明贪心选择性质

常用贪心套路

如果觉得这篇博客对你有帮助，欢迎点赞收藏！下一篇我们将讲解「回溯法」