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, 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>

int cmp(const void* a, const void* b) {
return (*(int*)a) – (*(int*)b);
}

int findContentChildren(int* g, int gSize, int* s, int sSize) {
qsort(g, gSize, sizeof(int), cmp);
qsort(s, sSize, sizeof(int), cmp);

int child = 0;
int cookie = 0;

while (child < gSize && cookie < sSize) {
if (s[cookie] >= g[child]) {
child++;
}
cookie++;
}

return child;
}

int main() {
int g[] = {1,2,3};
int s[] = {1,1};
int result = findContentChildren(g, 3, s, 2);
printf("满足的孩子数 = %d\\n", result);

int g2[] = {1,2};
int s2[] = {1,2,3};
result = findContentChildren(g2, 2, s2, 3);
printf("满足的孩子数 = %d\\n", result);
return 0;
}

代码实现（C++ 语言）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());

int child = 0;
int cookie = 0;

while (child < g.size() && cookie < s.size()) {
if (s[cookie] >= g[child]) {
child++;
}
cookie++;
}

return child;
}
};

int main() {
Solution sol;
vector<int> g = {1,2,3};
vector<int> s = {1,1};
int result = 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;
return 0;
}

复杂度分析

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

int wiggleMaxLength(int* nums, int numsSize) {
if (numsSize < 2) return numsSize;

int start = 0;
while (start < numsSize – 1 && nums[start] == nums[start + 1]) {
start++;
}
if (start == numsSize – 1) return 1;

int prevDiff = nums[start + 1] – nums[start];
int count = 2;

for (int i = start + 2; i < numsSize; i++) {
int diff = nums[i] – nums[i – 1];
if ((diff > 0 && prevDiff < 0) || (diff < 0 && prevDiff > 0)) {
count++;
prevDiff = diff;
}
}

return count;
}

int main() {
int nums[] = {1,7,4,9,2,5};
printf("最长摆动序列长度 = %d\\n", wiggleMaxLength(nums, 6));

int nums2[] = {1,17,5,10,13,15,10,5,16,8};
printf("最长摆动序列长度 = %d\\n", wiggleMaxLength(nums2, 10));
return 0;
}

代码实现（C++ 语言）

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2) return n;

int start = 0;
while (start < n – 1 && nums[start] == nums[start + 1]) {
start++;
}
if (start == n – 1) return 1;

int prevDiff = nums[start + 1] – nums[start];
int count = 2;

for (int i = start + 2; i < n; i++) {
int diff = nums[i] – nums[i – 1];
if ((diff > 0 && prevDiff < 0) || (diff < 0 && prevDiff > 0)) {
count++;
prevDiff = diff;
}
}

return count;
}
};

int main() {
Solution sol;
vector<int> nums = {1,7,4,9,2,5};
cout << "最长摆动序列长度 = " << sol.wiggleMaxLength(nums) << endl;
return 0;
}

例题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），…，可以跑完一圈。

思路分析

数学结论：

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>

int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) {
int totalGas = 0;
int totalCost = 0;
int tank = 0;
int start = 0;

for (int i = 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;
return start;
}

int main() {
int gas[] = {1,2,3,4,5};
int cost[] = {3,4,5,1,2};
printf("出发索引 = %d\\n", canCompleteCircuit(gas, 5, cost, 5));

int gas2[] = {2,3,4};
int cost2[] = {3,4,3};
printf("出发索引 = %d\\n", canCompleteCircuit(gas2, 3, cost2, 3));
return 0;
}

代码实现（C++ 语言）

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int totalGas = 0;
int totalCost = 0;
int tank = 0;
int start = 0;

for (int i = 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;
return start;
}
};

int main() {
Solution sol;
vector<int> gas = {1,2,3,4,5};
vector<int> cost = {3,4,5,1,2};
cout << "出发索引 = " << sol.canCompleteCircuit(gas, cost) << endl;
return 0;
}

三、贪心算法总结

什么时候用贪心？

优先考虑贪心，如果：

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

不要用贪心，如果：

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

常用贪心套路

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